Cod sursa(job #515998)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 22 decembrie 2010 21:26:46
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");

const int maxn=500005;
int i,N,K,v[maxn],D[maxn],Front,Back,amax,bmax,Max;

void citire()
{
	fin >> N >> K;
	for(i=1;i<=N;i++) fin >> v[i];
}

int main()
{
	citire();
	Front=1; Back=0;
	for(i=1;i<=N;i++) D[i]=-30001;
	Max=-30001;
	for(i=1;i<=N;i++)
	{
		while(Front<=Back && v[D[Back]] >= v[i])
			Back--;
		D[++Back]=i;
		if(i-K==D[Front]) Front++;
		if(i>=K && v[D[Front]]>Max)
		{
			Max=v[D[Front]];
			amax=i-K+1;
			bmax=i;
		}
	}
	fout << amax << " " << bmax << " " << Max;
}