Cod sursa(job #253163)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 15:08:24
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.76 kb
  #include <cstdio>  
  #define N 501200  
  int n,v[N],coada[N],p,u,max=-30001,a,b,k;  
   void read(){  
       int i,semn,x;  
       char sir[5*N];  
       freopen("secventa.in","r",stdin);  
       scanf("%d%d\n",&n,&k);  
       fgets(sir,5*N,stdin);  
       for (i = 0, x = 0, n = 0, semn = 1; sir[i]; ++i)  
       {  
           if (sir[i] == ' ')  
           {  
               v[++n] = x * semn;  
               x = 0;  
               semn = 1;  
           }  
           else if (sir[i] == '-')  
               semn = -1;  
           else if (sir[i] >= '0' && sir[i] <= '9')  
               x = x * 10 + (sir[i] - '0');  
       }  
       v[++n]=x*semn;  
   }   
   void elimin(int i){  
       while(p<u && coada[p]+k<=i)  
           ++p;  
   }  
   int caut(int x){  
       int p2=p,u2=u,m;  
       while(p2!=u2){  
           m=(p2+u2)/2;  
           if (x<=v[coada[m]])  
               u2=m;  
           else  
               p2=m+1;  
       }  
       if (v[coada[p2]]<x)  
           ++p2;  
       return p2;  
   }  
   void solve(){  
       int i,q;  
       coada[u++]=1;  
       for(i=2;i<=k;++i){  
           q=caut(v[i]);  
           u=q;  
           coada[u++]=i;  
       }  
       max=v[coada[0]];  
       a=1;  
       b=k;  
       for(i=k+1;i<=n;++i){  
           elimin(i);  
           q=caut(v[i]);  
           u=q;  
           coada[u++]=i;  
           if(v[coada[p]]>max){  
               max=v[coada[p]];  
               a=i-k+1;  
               b=i;  
          }  
       }  
   }  
   void write(){  
       freopen("secventa.out","w",stdout);  
       printf("%d %d %d\n",a,b,max);  
  }  
   int main(){  
       read();  
       solve();  
       write();