Cod sursa(job #1557184)

Utilizator geni950814Geni Geni geni950814 Data 26 decembrie 2015 22:58:15
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <fstream>
#include <deque>

using namespace std;

const int MAX = 500000;
int N, K, V[MAX];
deque<int> dq;

int main() {
	ifstream f("secventa.in");
	ofstream g("secventa.out");
	
	f >> N >> K;
	int min = -30001;
	int end = 0;
	for(int i = 1; i <= N ; i++) {
		f >> V[i];
		
		while(!(dq.empty()) && V[dq.back()] >= V[i]) {
			dq.pop_back();
		}
		dq.push_back(i);

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

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