Cod sursa(job #854697)

Utilizator blechereyalBlecher Eyal blechereyal Data 13 ianuarie 2013 20:56:29
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#define MAXN 5000001
#include <fstream>

using namespace std;
int K,N,A[MAXN],dq[MAXN];

ifstream f("secventa.in");
ofstream g("secventa.out");

void secv(){int p,u,i;
p=1;u=0;
int dr=0,max=-30333;


for (i=1;i<=N;i++)
    {
    while ((p<=u)&&(A[i]<=A[dq[u]])) u--;
    dq[++u]=i;
    if (dq[p]==i-K) p++;
    if ((i>=K)&&(A[dq[p]]>max)) {
        max=A[dq[p]];
        dr=i;
        }
    }
g<<dr-K+1<<" "<<dr<<" "<<max;
}

int main()
{
    f>>N>>K;
    for (int i=1;i<=N;i++) f>>A[i];
    secv();


    return 0;
}