Cod sursa(job #741822)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 27 aprilie 2012 02:26:47
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 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;
	}
};


int A[NMAX];


void readInput(int &numbersCount, int& sequenceLength, int * numbers, istream &cin)
{
	stringstream str;
	string line;

	getline(cin, line);
	str << line << "\n";
	str >> numbersCount
		>> sequenceLength;
		
	getline(cin, line);
	str << line << "\n";

	for(int i = 0 ; i < numbersCount; i++)
	{
		str >> numbers[i];
	}

}

void solve(int &numbersCount, int& sequenceLength, int * numbers, ostream &cout)
{
	deque<NumberInfo> deq;

	int sequenceStart;
	int sequenceBase;

	deq.push_back(NumberInfo(numbers[0], 0));

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

		deq.push_back(NumberInfo(numbers[i], i));
	}

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

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

		while(deq.empty() == false && deq.back().value > numbers[i])
		{
			deq.pop_back();
		}
		deq.push_back(NumberInfo(numbers[i], 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[])
{
	int numbersCount;
	int sequenceLength;
	int *numbers = (int*)&A;

	fstream fin(infile, ios::in);
	readInput(numbersCount, sequenceLength, numbers, fin);
	fin.close();

	fstream fout(outfile, ios::out);
	solve(numbersCount, sequenceLength, numbers, fout);
	fout.close();
}