Cod sursa(job #943939)

Utilizator predatorGigi Valoare predator Data 26 aprilie 2013 20:01:50
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include<cstdio>
#define NM 500100
using namespace std;
int A[NM],n,k,i,front,back,D[NM],ma,st,dr;
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
    ma=-900000;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i)
        scanf("%d",&A[i]);
    front=1;
    back=0;
    for(i=1;i<=n;++i)
    {
        while(front<=back&&A[i]<=A[D[back]]) D[back]=0,back--;
        D[++back]=i;
        if(D[front]==i-k) front++;
        if(i>=k&&A[D[front]]>ma)
            ma=A[D[front]],st=i-k+1,dr=i;
    }
    printf("%d %d %d",st,dr,ma);
    return 0;
}