Cod sursa(job #575077)

Utilizator AnteusPatrascoiu Mihai Anteus Data 7 aprilie 2011 21:18:11
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 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,lsf,ldf,m=-100000;


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

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

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

fout<<lsf<<" "<<ldf<<" "<<m;
return 0;
}