Cod sursa(job #1602628)

Utilizator aimrdlAndrei mrdl aimrdl Data 16 februarie 2016 20:49:17
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <iostream>
#include <list>

using namespace std;

struct item {
	int val;
	int pos;
};

int main (void) {
	ios_base::sync_with_stdio(false);
	
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
		
	int n, k;
	
	cin >> n >> k;
	int v[n];
	
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
	}
	
	list<item> l;
	item aux = {v[0], 0};
	l.push_back(aux);
	
	int max = v[0], startSol = 0;
	
	for (int i = 1; i < n; ++i) {		
		while (!l.empty() && v[i] <= l.back().val) {
			l.pop_back();
		}
		
		aux.val = v[i];
		aux.pos = i;
		l.push_back(aux);
		
		if (l.front().pos <= i - k) l.pop_front();
		
		if (l.front().val > max) {
			max = l.front().val;
			startSol = l.front().pos;
		}
	}
	
	
	cout << startSol + 1 << " " << startSol + k << " " << max;
	
	return 0;
}