Cod sursa(job #1197656)

Utilizator taigi100Cazacu Robert taigi100 Data 13 iunie 2014 09:16:39
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 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, Back = 0;
    for(int i=1;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 = Deque[Front];
            }
        }
    }
    g << beg << " " << beg+K-1 << " " << best;

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