Cod sursa(job #741827)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 27 aprilie 2012 03:08:59
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <string.h>

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 readNextInt(char* sir)
{
	char* p = sir;
	int result = 0;
	bool isNegative = false;

	if(*p == '-')
	{
		p++;
		isNegative = true;
	}

	while(*p)
	{
		result *= 10;
		result += *p - '0';
		p++;
	}

	if(isNegative == true) 
		result = -result;
	return result;
}


char sir [NMAX * 8];

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

	int sequenceLength;
	int numbersCount;

	cin >> numbersCount
		>> sequenceLength;

	cin.getline(sir, 1);
	cin.getline(sir, NMAX * 8);

	int currentNumber;
	int sequenceStart;
	int sequenceBase;

	char *p;	
	p = strtok(sir, " ");
	currentNumber = readNextInt(p);

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

	for(int i = 1; i < numbersCount; i++)
	{
		p = strtok(NULL, " ");
		currentNumber = readNextInt(p);

		if(deq.empty() == false && 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(i >= sequenceLength)
		{
			if(deq.front().value > sequenceBase)
			{
				sequenceBase = deq.front().value;
				sequenceStart = i - sequenceLength + 1;
			}
		}
		else if(i == sequenceLength - 1)
		{
			sequenceStart = 0;
			sequenceBase = deq.front().value;
		}
	}

	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();
}