Cod sursa(job #943937)

Utilizator predatorGigi Valoare predator Data 26 aprilie 2013 19:58:13
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.48 kb
#include<fstream>
#define NM 500100
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int A[NM],n,k,i,front,back,D[NM],ma,st,dr;
int main()
{
	ma=-900000;
	f>>n>>k;
	for(i=1;i<=n;++i)
		f>>A[i];
	front=1;
	back=0;
	for(i=1;i<=n;++i)
	{
		while(front<=back&&A[i]<=A[D[back]]) D[back]=0,back--;
		D[++back]=i;
		if(D[front]==i-k) front++;
		if(i>=k&&A[D[front]]>ma)
			ma=A[D[front]],st=i-k+1,dr=i;
	}
	g<<st<<" "<<dr<<" "<<ma;
	return 0;
}