Cod sursa(job #253159)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 15:01:37
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.08 kb
   #include<stdio.h>  
   const int N=500001;  
   int start,end,deque[N];  
   char buff[N*8],*c;  
   int read()  
   {  
       int sgn=1,val=0;  
       if(*c=='-'){ sgn=-1; ++c; }  
       while(*c>='0'&&*c<='9')  
       {  
           val=val*10+*c-'0';  
           ++c;  
       }  
       ++c;  
       return val*sgn;  
   }  
   int main()  
   {  
       freopen("secventa.in","r",stdin);  
       freopen("secventa.out","w",stdout);  
       int v[N],deque[N],n,k;  
       int i,l,max=-30001;  
       scanf("%d%d\n",&n,&k);  
       fgets(buff,8*N,stdin);  
       c=buff;  
       for(i=1;i<=n;++i)  
           v[i]=read();  
       start=1;  
       end=0;  
       for(i=1;i<=n;++i)  
       {  
           while(start<=end&&v[deque[end]]>=v[i]) --end;  
           deque[++end]=i;  
           if(deque[start]==i-k) ++start;  
           if(v[deque[start]]>max&&i>=k)  
           {  
               max=v[deque[start]];  
               l=i;  
           }  
       }  
       printf("%d %d %d\n",l-k+1,l,max);  
       return 0;  
   }