Cod sursa(job #659298)

Utilizator ilucianIlea Lucian ilucian Data 10 ianuarie 2012 14:46:48
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream fi("secventa.in");
ofstream fo("secventa.out");
int N,K,i;
int v1,v2;
int X[500001];
deque <int> D;
deque <int> :: iterator it;
int st,dr;
int rez;
int main()
{
	fi>>N>>K;
	for (i=1;i<=N;i++)
		fi>>X[i];
	rez=-100000;
	for (i=1;i<=N;i++)
	{
		while (!D.empty() && i-D.front()>=K)
			D.pop_front();
		while (!D.empty() && X[D.back()]>X[i])
			D.pop_back();
		if (D.empty() || (!D.empty() && X[D.back()]<=X[i]))
			D.push_back(i);
		v1=D.front();
		v2=D.back();
		if (X[D.front()]>rez && i-D.front()+1>=K)
		{
			rez=X[D.front()];
			st=D.front();
			dr=i;
		}
	}
	fo<<st<<" "<<dr<<" "<<rez;
	fi.close();
	fo.close();
	return 0;
}