Cod sursa(job #2051921)

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

int main()
{
    ifstream f("secventa.in");
    int N, K;
    f >> N >> K;

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

    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);

        while (i - dq.front() + 1 > K && dq.front() < arr[i])
            dq.pop_front();

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

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

    return 0;
}