Cod sursa(job #1554210)

Utilizator geni950814Geni Geni geni950814 Data 21 decembrie 2015 05:03:36
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <deque>
#include <iostream>

using namespace std;

const int MAX = 500000;
int N, K, V[MAX];

int main() {
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	
	f >> N >> K;
	deque<int> deque;
	int min = V[0];
	int start = 0;
	int end = 0;

	for(int i = 0; i < N; i++) {
		f >> V[i];
		int newStart = start;
		int newEnd = end;
		if(!(deque.empty()) && deque.front() <= i - K) {
			deque.pop_front();
			newStart = deque.front();
		}
		while(!(deque.empty()) && V[deque.back()] >= V[i]) {
			deque.pop_back();
		}
		deque.push_back(i);
		newEnd = i;

		if(i >= K-1 && min <= V[deque.front()]) {
			min = V[deque.front()];
			start = newStart;
			end = newEnd;
		}
	}
	g << start + 1 << " " << end + 1 << " " << min << endl;
	return 0;
}