Cod sursa(job #575075)

Utilizator AnteusPatrascoiu Mihai Anteus Data 7 aprilie 2011 21:14:57
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <stdio.h>
#include <deque>
using namespace std;
FILE *f=fopen ("secventa.in", "r");
FILE *g=fopen ("secventa.out", "w");
deque <int> dq;
int v[500001],i,n,k,ls,ld,lsf,ldf,m=-100000;


int main() {
fscanf (f, "%d%d", &n,&k);

for (i=1;i<=n;i++)
{
	fscanf (f, "%d", &v[i]);

	while (!dq.empty() && dq[0]<i-k+1)
	{
		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;
		}
	}
}

fprintf (g, "%d %d %d", lsf,ldf,m);
return 0;
}