Cod sursa(job #716405)

Utilizator teodora.petrisorPetrisor Teodora teodora.petrisor Data 18 martie 2012 19:07:17
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#define DIM 500001

using namespace std;

int a[DIM],n,k,st,en,base;

void read()
{
	ifstream f ("secventa.in");
	int i;
	f>>n>>k;
	for (i=1;i<=n;i++)
		f>>a[i];
	f.close();
}

void print()
{
	ofstream g ("secventa.out");
	g<<st<<" "<<en<<" "<<base<<endl;
	g.close();
}

void detSol()
{
	int r,l,i,deque[DIM];
	l=r=1;
	deque[1]=1;
	base=-DIM;
	for (i=2;i<k;i++)
	{
		while (a[deque[r]]>=a[i]&&r>=l)
			r--;
		r++;
		deque[r]=i;
	}
	for(i=k;i<=n;i++)
	{
		while (a[deque[r]]>=a[i]&&r>=l)
			r--;
		r++;
		deque[r]=i;
		if (a[deque[l]]>base)
		{
			base=a[deque[l]];
			st=i-k+1;
			en=i;
		}
		if (deque[l]<i-k+2)
			l++;
	}
	}

int main()
{
	read();
	detSol();
	print();
	return 0;
}