Cod sursa(job #232517)

Utilizator MciprianMMciprianM MciprianM Data 15 decembrie 2008 17:38:12
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 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;  
    //while(a[ult]>x && ult>=vf)  ult--;  
    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;  
}