Cod sursa(job #1554223)

Utilizator geni950814Geni Geni geni950814 Data 21 decembrie 2015 06:19:09
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 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 = -30001;
	int end = 0;
	for(int i = 1; i <= N ; i++) {
		f >> V[i];
		
		while(!(deque.empty()) && V[deque.back()] >= V[i]) {
			deque.pop_back();
		}
		deque.push_back(i);

		if(deque.front() <= i-K) {
			deque.pop_front();
		}

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