Cod sursa(job #169610)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 1 aprilie 2008 20:23:56
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>
const int nmax=500001;
int n,k,ls,ld,i,p,min,a[nmax],q[nmax],prim,ult;
char buffer[nmax];
int main(){
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    setbuf(stdin,buffer);
    scanf("%d %d",&n,&k);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    ls=1;ld=k;
    prim=ult=1;q[1]=1;
    for (i=2;i<=k;i++){
        while (ult>=prim && a[q[ult]]>a[i]) ult--;
        q[++ult]=i;
        }
    min=a[q[prim]];
    for (i=k+1;i<=n;i++){
        while (prim<=ult && i-q[prim]+1>k) prim++;
        while (ult>=prim && a[q[ult]]>a[i]) ult--;
        q[++ult]=i;
        if (a[q[prim]]>min) {min=a[q[prim]];
                             ls=i-k+1;
                             ld=i;}
        }
    printf("%d %d %d",ls,ld,min);
    return 0;
}