Cod sursa(job #2051941)

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

int nextInt(string &line, int &pos)
{
    if (pos < line.size())
    {
        int n = 0;
        while (line[pos] != ' ' && line[pos] != '\n')
            n = n * 10 + (line[pos++] - '0');
        pos++;
        return n;
    }

    return -1;
}

int main()
{
    ifstream f("secventa.in");
    string line;
    int pos = 0;
    getline(f, line, '~');
    int N = nextInt(line, pos);
    int 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;
}