Cod sursa(job #741818)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 27 aprilie 2012 01:46:41
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

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

#define NMAX 500001

int A[NMAX];

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

void readInput(int &numbersCount, int& sequenceLength, int * numbers, istream &cin)
{
	cin >> numbersCount
		>> sequenceLength;
		
	for(int i = 0 ; i < numbersCount; i++)
	{
		cin >> 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();
}