Cod sursa(job #741823)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 27 aprilie 2012 02:37:21
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <sstream>
using namespace std;

const char infile[] = "secventa.in";
const char outfile[] = "secventa.out";

#define NMAX 500001

struct NumberInfo
{
	int value;
	int position;
	NumberInfo()
	{

	}
	NumberInfo(int value, int position)
	{
		this->value = value;
		this->position = position;
	}
};

void solve( istream &cin, ostream &cout )
{
	deque<NumberInfo> deq;

	int sequenceLength;
	int numbersCount;

	cin >> numbersCount
		>> sequenceLength;


	int currentNumber;
	int sequenceStart;
	int sequenceBase;

	cin >> currentNumber;
	deq.push_back(NumberInfo(currentNumber, 0));

	for(int i = 1; i < sequenceLength; i++)
	{
		cin >> currentNumber;
		while(deq.empty() == false && deq.back().value > currentNumber)
		{
			deq.pop_back();
		}

		deq.push_back(NumberInfo(currentNumber, i));
	}

	sequenceStart = 0;
	sequenceBase = deq.front().value;

	for(int i = sequenceLength; i < numbersCount; i++)
	{
		cin >> currentNumber;
		if(deq.front().position <= i - sequenceLength)
		{
			deq.pop_front();
		}

		while(deq.empty() == false && deq.back().value > currentNumber)
		{
			deq.pop_back();
		}
		deq.push_back(NumberInfo(currentNumber, i));

		if(deq.front().value > sequenceBase)
		{
			sequenceBase = deq.front().value;
			sequenceStart = i - sequenceLength + 1;
		}
	}

	sequenceStart += 1;
	cout << sequenceStart << " "
		 << sequenceStart + sequenceLength - 1 << " "
		 << sequenceBase << "\n";

}

int main(int argc, char* argv[])
{
	fstream fin(infile, ios::in);
	fstream fout(outfile, ios::out);

	solve(fin, fout);

	fin.close();
	fout.close();
}