Cod sursa(job #555791)

Utilizator feelshiftFeelshift feelshift Data 15 martie 2011 19:32:03
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
// http://infoarena.ro/problema/secventa
#include <fstream>
#include <deque>
using namespace std;

const int maxSize = 500001;
const int oo = 0x3f3f3f3f;

ifstream in("secventa.in");
ofstream out("secventa.out");

int number[maxSize];

int main() {
	int length,requestedLength;

	in >> length >> requestedLength;
	for(int i=1;i<=length;i++)
		in >> number[i];

	int minim = -oo;
	pair<int,int> position;
	deque<int> myDeque;
	for(int i=1;i<=length;i++) {
		while(!myDeque.empty() && number[myDeque.back()] >= number[i])
			myDeque.pop_back();

		myDeque.push_back(i);

		if(myDeque.front() == i - requestedLength)
			myDeque.pop_front();
		
		if(minim < number[myDeque.front()] && i >= requestedLength) {
			minim = number[myDeque.front()];
			position = make_pair(i-requestedLength+1,i);
		}
	}

	out << position.first << " " << position.second << " " << minim << "\n";

	in.close();
	out.close();

	return (0);
}