Cod sursa(job #429715)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 30 martie 2010 13:31:36
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <deque>

#define NMAX 500100
#define mp make_pair
using namespace std;

deque<pair<int, int> > DQ;
int A[NMAX], N, best, besti, K;

void readAll(void)
{
	ifstream fin("secventa.in");
	
	fin >>N >>K;
	
	for (int i = 1; i <= N; i++)
		fin >>A[i];
	
	fin.close();
}
void Solve(void)
{
	int i;
	
	for (i = 1; i < K; i++)
	{
		while (!DQ.empty() && DQ.back().first >= A[i]) DQ.pop_back();
		DQ.push_back( mp(A[i], i) );
	}
	for (; i <= N; i++)
	{
		if (DQ.front().second <= i - K)
			DQ.pop_front();
		
		while (!DQ.empty() && DQ.back().first >= A[i]) DQ.pop_back();
		DQ.push_back( mp(A[i], i) );
		
		if (DQ.front().first > best) 
		{
			best = DQ.front().first;
			besti = i;
		}
	}
}
void writeAll(void)
{
	ofstream fout("secventa.out");
	
	fout <<besti - K + 1 <<' ' <<besti <<' ' <<best <<'\n';
	
	fout.close();
}

int main()
{
	readAll();
	
	Solve();
	
	writeAll();
	
	return 0;
}