Cod sursa(job #1760871)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 21 septembrie 2016 13:32:20
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int solution = -100000000, first, last, A[600010], N, K;
deque<int>deq;

int main()
{
    fin >> N >> K;

    for(int i = 1; i <= N; i ++)
    {
        fin >> A[i];
    }

    for(int i = 1; i <= N; i ++)
    {
        while( !deq.empty() && A[i] < A[deq.back()])
        {
            deq.pop_back();
        }

        deq.push_back(i);

        if(i - deq.front() >= K)
        {
            deq.pop_front();
        }

        if(i >= K && solution < A[deq.front()])
        {
            if(i - deq.front() < K - 1)
            {
                first = i - K + 1;
                last = i;
                solution = A[deq.front()];
            }
            else
            {
                first = deq.front();
                last = i;
                solution = A[deq.front()];
            }
        }
    }

    fout << first << " " << last << " " << solution;

    return 0;
}