Cod sursa(job #741819)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 27 aprilie 2012 02:04:13
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <iostream>
#include <fstream>
#include <deque>
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];

template <class T>
class Deque
{
public:

	Deque(int maxSize)
	{
		this->_elements = new NumberInfo[maxSize];
		this->_start = -1;
		this->_end = -1;
	}

	~Deque()
	{
		delete _elements;
	}

	NumberInfo front()
	{
		return this->_elements[_start];
	}

	NumberInfo back()
	{
		return this->_elements[_end];
	}

	bool empty()
	{
		if(_end < _start || this->_start == -1)
			return true;
		return false;
	}

	void pop_back()
	{
		this->_end --;
	}

	void push_back(T element)
	{
		if(this->empty() == true)
		{
			this->_start = 0;
			this->_end = -1;
		}

		this->_end++;
		this->_elements[_end] = element;
	}

	void pop_front()
	{
		this->_start++;
	}
protected:
private:
	int _start;
	int _end;
	T *_elements;
};


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;
	Deque<NumberInfo> deq(numbersCount);

	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, cout);
	fout.close();
}