Cod sursa(job #2051951)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 29 octombrie 2017 19:26:11
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <deque>
#include <limits>
using namespace std;

int nextInt(string &line, int &pos)
{
    int n = 0;
    bool read = false;
    bool negative = false;
    do
    {
        if (line[pos] == '-')
            negative = true;

        while (line[pos] >= '0' && line[pos] <= '9')
        {
            read = true;
            n = n * 10 + (line[pos++] - '0');
        }
        pos++;
    } while (!read);

    if (negative)
        n = -n;
    return n;
}

int main()
{
    ifstream f("secventa.in");
    string line;
    getline(f, line, '~');
    int pos = 0;
    int N = nextInt(line, pos), K = nextInt(line, pos);

    int arr[N + 1], currentBase;
    int finalLeft, finalRight, finalBase = 0;
    arr[0] = numeric_limits<int>::min();
    for (int i = 1; i <= N; i++)
        arr[i] = nextInt(line, pos);

    f.close();

    deque<int> dq;
    for (int i = 1; i < K; i++)
    {
        while (!dq.empty() && arr[dq.back()] >= arr[i])
            dq.pop_back();
        dq.push_back(i);
    }

    for (int i = K; i <= N; i++)
    {
        while (!dq.empty() && arr[dq.back()] >= arr[i])
            dq.pop_back();
        dq.push_back(i);

        if (i - dq.front() + 1 > K)
            dq.pop_front();

        currentBase = dq.front();
        if (arr[currentBase] > arr[finalBase])
        {
            finalBase = currentBase;
            finalLeft = currentBase;
            finalRight = i;
        }
    }

    while (finalLeft - 1 > 0 && arr[finalLeft - 1] >= arr[finalBase])
        finalLeft--;

    ofstream g("secventa.out");
    g << finalLeft << " " << finalRight << " " << arr[finalBase];
    g.close();

    return 0;
}