Cod sursa(job #711926)

Utilizator IGS_013Ivanciuc Gheorghe Stefan IGS_013 Data 12 martie 2012 21:20:41
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
# define MAX 500013
#include<fstream>
#include<iostream>

int n,k;
int h[MAX];
int start, stop, valmax;

void Citire()
{
	std::ifstream f;
	f.open ("secventa.in");
	f>>n>>k;
	for(int i = 1 ; i <= n ; i++)
		f>>h[i];
	f.close();
}

void Afisare()
{
	std::ofstream g;
	g.open ("secventa.out");
	g<<start<<" "<<stop<<" "<<valmax;
	g.close();
}

void KSecv()
{
	int deque[MAX];
	int st=1, dr=1;
	deque[1]=1;
	valmax=-MAX;

	for(int i=2;i<k;i++)
		{
			while (h[deque[dr]]>=h[i] && dr>=st)
				dr--;
			dr++;
			deque[dr]=i;
		}
	for(int i=k;i<=n;i++)
		{
			while (h[deque[dr]]>=h[i] && dr>=st)
				dr--;
			dr++;
			deque[dr]=i;
			if (h[deque[st]]>valmax)
				{
					valmax=h[deque[st]];
					start=i-k+1;
					stop=i;
				}
			if (deque[st]<i-k+2)
				st++;
		}

	Afisare();
}

int main()
{
	Citire();
	KSecv();
	return 0;
}