Cod sursa(job #329028)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 4 iulie 2009 14:42:45
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<fstream>
#include<deque>
#define MaxN 500005
#define INF 0x3f3f3f3f
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

deque<int> deq;
int a[MaxN];
int st,dr,n,k,i,Max=-INF;

int main()
{	fin>>n>>k;
	for(i=1;i<=n;i++) fin>>a[i];
	for(i=1;i<=n;i++)
	{	while(!deq.empty()&&a[i]<=a[deq.back()]) deq.pop_back();
		deq.push_back(i);
		if(deq.front()<=i-k) deq.pop_front();
		if(i>=k&&a[deq.front()]>Max)
		{	Max=a[deq.front()];
			dr=i;
		}
	}
	fout<<dr-k+1<<' '<<dr<<' '<<Max<<'\n';
	return 0;
}