Cod sursa(job #253174)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 15:15:48
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
 #include<stdio.h>  
 #include<stdlib.h>  
 #include<string.h>  
 int x[50011],v[500011],k,n,i,p,q,m,a,b,max=-50000,st;  
 char ch[500001<<3];  
 int main(){  
 freopen("secventa.in","r",stdin);  
 scanf ("%d %d\n",&n,&k);  
 gets(ch);  
 v[1]=atoi(strtok(ch," \n"));  
 for(i=2;i<=n;i++)  
         v[i]=atoi(strtok(NULL," \n"));     
 x[1]=1;  
 p=1;q=1;  
 for(i=2;i<=n;i++)  
         {while(x[p]<i-k+1) p++;  
   
         while(v[i]<v[x[q]]  &&  p<=q)  
   
                 q--;  
         q++;  
         x[q]=i;  
         if(i==k)  
                 {max=v[x[1]];st=1;}  
         else  
           
         if(v[x[p]]>max&&i>k)  
                 {max=v[x[p]];  
                 st=i-k+1 ;  
                 }  
        }  
 FILE *g=fopen("secventa.out","w");  
 fprintf(g,"%d %d %d",st,(st+k-1),max);  
 fclose(g);  
 return 0;}