Cod sursa(job #278836)

Utilizator andreivFMI - vacaroiu andrei andreiv Data 12 martie 2009 15:50:15
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
 #include <stdio.h>  
 #define N 500*1001  
 #define M N*7  
   
 int n,k,p,u,a[N],x,y,max=-100000,d[N],i;  
 char s[M];  
   
 void parsare()  
 {  
      int i,j,c;  
        
     fgets(s,M,stdin);  
      for(i=1,j=0;i<=n;i++)   
          {    
           while(s[j]==' ') j++;    
          if(s[j]=='-') { c=1; j++; }   
              else c=0;   
           while(s[j]>='0' && s[j]<='9') a[i]=a[i]*10+s[j++]-48;   
         if (c) a[i]*=-1;   
          }    
 }  
   
 int main()  
 {  
     freopen("secventa.in","r",stdin);  
     freopen("secventa.out","w",stdout);  
    scanf("%d %d\n", &n, &k);  
     parsare();  
     p=1; u=0;  
     for (i=1;i<=n;++i)  
         {  
          while (p<=u && a[i]<=a[d[u]])  
                u--;  
          d[++u]=i;  
          if (d[p]==i-k) ++p;  
         if (i>=k)   
           if (a[d[p]]>max)   
                            {  
                             max=a[d[p]];  
                             x=i-k+1;  
                             y=i;  
                            }   
        }  
     printf("%d %d %d", x, y, max);  
    return 0;  
}