Cod sursa(job #169672)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 1 aprilie 2008 20:55:27
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <string.h>
#include <stdlib.h>
const int nmax=500001;
int n,k,ls,ld,i,p,min,a[nmax],q[nmax],prim,ult,semn;
char buffer[nmax*6+1],*s;
int main(){
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    gets(buffer); 
    s=buffer;
    for(i=1;i<n;i++)  
     {a[i]=atoi(s); 
      s=strchr(s,' '); 
      s++;  
      }  
    a[n]=atoi(s);                 
    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;
}