Cod sursa(job #575086)

Utilizator AnteusPatrascoiu Mihai Anteus Data 7 aprilie 2011 21:31:05
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.48 kb
#include <fstream.h>
#include <deque>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
deque <int> dq;
int v[500001],i,n,k,ls,ld,m=-100000;


int main() {
fin>>n>>k;

for (i=1;i<=n;i++)
{
	fin>>v[i];

	if (dq[0]==i-k)
		dq.pop_front();
	
	while (!dq.empty() && v[dq.back()]>v[i])
		dq.pop_back();
	dq.push_back(i);
	
	if (i>=k && m<v[dq.front()] )
	{
		m=v[dq.front()];	ls=i-k+1;	ld=i;
	}
}

fout<<ls<<" "<<ld<<" "<<m;
return 0;
}