Cod sursa(job #1197659)

Utilizator taigi100Cazacu Robert taigi100 Data 13 iunie 2014 09:28:04
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
/*
    Keep It Simple!
*/

#include<fstream>
using namespace std;
#define MaxN 500005

int A[MaxN],Deque[MaxN],N,K,best,beg;

int main()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");
    best = -(1<<30);
    f >> N >> K;
    for(int i=1;i<=N;i++)
        f >> A[i];
    int Front = 1;
    int Back = 1;
    Deque[1] = 1;
    for(int i = 2; i < K; ++i)
    {
             while(Front <= Back && A[i] <= A[ Deque[Back] ]) Back--;
             Deque[++Back] = i;
    }
    for(int i=K;i<=N;i++)
    {
        while(Front <= Back && A[i] <= A[Deque[Back]]) Back--;
        Deque[++Back] = i;

        if(Deque[Front] == i-K) Front++;

        if(i>=K)
        {
            if(A[Deque[Front]] > best)
            {
                best = A[Deque[Front]];
                beg = i;
            }
        }
    }
    g << beg-K+1 << " " << beg << " " << best;

    f.close();
    g.close();
    return 0;
}