Cod sursa(job #205142)

Utilizator MciprianMMciprianM MciprianM Data 29 august 2008 14:38:20
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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;pas;pas>>=1)
      if(a[tz+pas]<=x && tz+pas<=ult)
        tz+=pas;
    ult=tz+1;
    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;pas<<=1);
    for(tz=vf;pas;pas>>=1)
      if(a[tz+pas]<=x && tz+pas<=ult)
        tz+=pas;
    ult=tz+1;
    //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;
}