Cod sursa(job #103645)

Utilizator MariazBurlacu Maria Mariaz Data 15 noiembrie 2007 15:35:11
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 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;
}