Cod sursa(job #159226)

Utilizator city_guy91alex isip city_guy91 Data 14 martie 2008 00:05:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
 #include <fstream>  
 #define Nmax 500001  
 #define MAX 3000001  
   
 using namespace std;  
   
 int V[Nmax], Q[Nmax];  
 char buffer[MAX];  
 int p;  
   
 void ins(int &x)  
     {x=0;  
      int k=buffer[p]=='-'?p++, k=-1 : k=1;  
      for( ; buffer[p]>='0' && buffer[p]<='9' ; p++)  
              x = x*10 + buffer[p] - '0';  
      x*=k;      
     }           
                 
   
 int main(void)  
     {int n, k;  
      freopen("secventa.in", "r", stdin);  
      freopen("secventa.out", "w", stdout);  
      fread(buffer, 1, MAX, stdin);  
      ins(n);  
      p++;  
      ins(k);  
      p++;  
            
      int i, ind=1;  
      for(i=1;i<=n;i++)  
          {ins(V[i]);  
           p++;  
          }   
                 
          
        
      int max=-Nmax, p=0;  
      int end=0, beg=1;  
        
        
      //printf("%d\n", V[1]);  
      for(i=1;i<=n;++i)  
           {  
            if(beg <= end && Q[beg]<= i-k) beg++;  
              
            while(beg<=end &&  V[ Q[end] ]>V[i]) end--;  
              
            Q[++end]=i;  
            if(V[Q[beg]]>max && i>=k) {max=V[Q[beg]]; p=i;}  
            //printf("%d\n", V[Q[beg]]);  
           }  
             
        
      printf("%d %d %d\n", p-k+1, p, max);  
        
      return 0;  
  }