Cod sursa(job #97717)

Utilizator MatricMatache Alexandra Matric Data 8 noiembrie 2007 08:39:32
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream.h>
#define maxim 500001
ifstream f("secventa.in");
ofstream g("secventa.out");
int first,last;
int deque[maxim][2];
int n,l,a[500000],maxsol=-1000000,p,q,i,min;
int main()
{   f>>n>>l;
    for (i=1;i<=n;++i) f>>a[i];
	for (i=1;i<l;++i) {
						while (first<=last && deque[last][0]>a[i]) --last;
						++last;
						deque[last][0]=a[i];
						deque[last][1]=i;
	                  }
	for (i=l;i<=n;i++){	
		                while (first<=last && deque[last][0]>a[i]) --last;
						++last;
						deque[last][0]=a[i];
						deque[last][1]=i;
						while (first<=last && deque[first][1]<i-l+1) ++first;
	                    int min=deque[first][0];
						if (min>maxsol) { maxsol=min;
						                  p=i-l+1;
										  q=i;
						                } 
	                  }
	g<<p<<" "<<q<<" "<<maxsol;	
	return 0;
}