Cod sursa(job #156612)

Utilizator vicenzo_cnuStan Alexandru Dan vicenzo_cnu Data 12 martie 2008 17:39:03
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
    #include <iostream>  
    #include <cstdio>  
    #include <utility>  
    using namespace std;

    #define mp make_pair
    #define f first
    #define s second
    //#define __debug__

   #ifdef __debug__  
   const long MAX = 5000;  
   #else  
   const long MAX = 500010;  
   #endif  
     
   char buf[7*MAX];  
  long  Dequef[MAX], Deques[MAX];  
   long p,u;  
   long n,k,i,x;  
   long st, dr, m=-0x3f3f3f;  
   long nr;  
     
   void print() {  
       for (long i=p; i<u; ++i)  
           printf("(%ld %ld) ", Dequef[i], Deques[i]);  
       printf("\n");  
   }  
     
   inline void push(long inf, long ins) {  
       while ( p<u && inf-Dequef[p]>=k )  
           ++p;  
       if ( ins<Deques[p] ) {  
           while ( ins<Deques[p] && p<u )   
               ++p;  
           Dequef[p] = inf; Deques[p] = ins;  
           if ( p==u ) ++u;  
       } else {  
           while ( ins<Deques[u-1] )  
               --u;  
           Deques[u] = ins;  
           Dequef[u++] = inf;  
       }  
   //  print();  
   }  
     
   inline long nrc(long x) {  
       long ret = 0;  
       if ( x<=0 ) ret++, x=-x;  
       for (; x; x/=10) ret++;  
       return ret;  
   }  
     
   bool ok;  
     
   int main() {  
       freopen("secventa.in", "r", stdin);  
       scanf("%ld %ld\n", &n, &k);  
       fgets(buf, 7*MAX, stdin);  
       for (i=0; i<k-1; ++i) {  
           ok = 0;  
           if ( buf[nr]=='-' )  
               ++nr, ok=1;  
           for (x=0; buf[nr]<='9' && buf[nr]>='0'; ++nr)  
               x = x*10 + buf[nr]-'0';  
           ++nr;  
           if ( ok ) x*=-1;  
           push(i, x);  
       }  
       for ( i=k-1; i<n; ++i) {  
           ok = 0;  
           if ( buf[nr]=='-' )  
               ++nr, ok=1;  
           for (x=0; buf[nr]<='9' && buf[nr]>='0'; ++nr)  
               x = x*10 + buf[nr]-'0';  
           ++nr;  
           if ( ok ) x *= -1;  
           push(i, x);  
           if ( Deques[p] > m ) {  
               st = i-k+1; dr = i;  
               m = Deques[p];  
           }  
       }  
     
       fprintf(fopen("secventa.out", "w"), "%ld %ld %ld\n", st+1, dr+1, m);  
       return 0;  
  }