Cod sursa(job #719082)

Utilizator avram_florinavram florin constantin avram_florin Data 21 martie 2012 13:46:27
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
#include<cstdio>

using namespace std;

const int MaxN = 500001;

const char InFile[] = "secventa.in";
const char OutFile[] = "secventa.out";

int N,K,v[MaxN],deque[MaxN];

int main()
{
	ifstream fin( InFile );
	ofstream fout( OutFile );
	fin >> N >> K;
	int i,left,right;
	for( i = 1 ; i <= N ; ++i )
		fin >> v[i];
	left = right = 1;
	deque[1] = 1;
	for( i = 2 ; i < K ; ++i )
		{
			while( v[deque[right]] >= v[i] && right >= left )
				--right;
			deque[++right] = i;
		}
	int baza,poz;
	baza = poz = -32001;
	for( i = K ; i <= N ; ++i )
		{
			while( v[deque[right]] >= v[i] && right >= left )
				--right;
			deque[++right] = i;
			if( v[deque[left]] > baza )
				{
					baza = v[deque[left]];
					poz = i+1-K;
				}
			if( deque[left] < i - K + 2 )
				++left;
		}
	fout << poz << ' ' << poz+K-1 << ' ' << baza << '\n';
	fin.close();fout.close();
	return 0;
}