Cod sursa(job #97526)

Utilizator gigi_becaliGigi Becali gigi_becali Data 7 noiembrie 2007 15:11:44
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<fstream.h>
ifstream f("secventa.in");
ofstream g("secventa.out");
int first,last,maxsol=-1000000,p,q,min,i;
int dq[500000][2];
int n,L,a[500000];
int main()
{f>>n>>L;
 for(i=1;i<=n;++i)f>>a[i];
 for(i=1;i<L;++i)
 {while(first<=last&&dq[last][0]>a[i])--last;
  ++last;
  dq[last][0]=a[i];
  dq[last][1]=i;
 }
 
 for(i=n;i<=L;i++){while(first<=last&&dq[last][0]>a[i])--last;
  ++last;
  dq[last][0]=a[i];
  dq[last][1]=i;
  while(first<=last&&dq[first][1]<i-L+1)++first;
  int min=dq[first][0];
  if(min>maxsol){maxsol=min;
		         p=i-L+1;
				  q=i;
				  }
 }
g<<p<<" "<<q<<" "<<maxsol<<"\n";
f.close();
g.close();
return 0;
}