Cod sursa(job #253153)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 14:55:04
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
 include<fstream>    
 using namespace std;    
 int a[500009];    
 int b[500009];    
 int main(){    
   int n, k, i, vf, ult,x,pi,psf,bmax, pas,tz;    
   ifstream f("secventa.in");    
   f>>n>>k;    
   vf=0;    
   ult=-1;    
   for(i=0;i<k;i++){    
     f>>x;    
     for(pas=1;pas<=ult;pas<<=1);    
     for(tz=vf-1;pas;pas>>=1)    
       if(a[tz+pas]<x && tz+pas<=ult)    
         tz+=pas;    
     ult=tz;    
     if(ult<vf)    
      ult=vf=0;    
     else    
       ++ult;    
     a[ult]=x;    
     b[ult]=i+1;      
   }    
   pi=1;psf=k;bmax=a[vf];    
   for(i=k+1;i<=n;i++){    
     if(b[vf]<i-k+1) vf++;    
     f>>x;    
     for(pas=1;vf+pas<ult+2;pas<<=1);    
     for(tz=vf-1;pas;pas>>=1)    
       if(a[tz+pas]<x && tz+pas<=ult)    
         tz+=pas;    
     ult=tz;    
     if(ult<vf)    
       ult=vf;    
     else ++ult;    
     a[ult]=x;    
     b[ult]=i;    
     if(a[vf]>bmax){bmax=a[vf];psf=i;pi=i-k+1;}    
   }    
   f.close();    
   ofstream g("secventa.out");    
   g<<pi<<' '<<psf<<' '<<bmax<<'\n';    
   g.close();    
   return 0;    
 }