Cod sursa(job #1370566)

Utilizator PikachuPikachu Pikachu Data 3 martie 2015 15:47:09
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>
#include <deque>

using namespace std;

const int NMAX = 500000;

int v[NMAX + 5];
deque <int> dq;

int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	int n, k, sol = -(1 << 30), is, js;

	scanf("%d%d", &n, &k);

	for(int i = 1; i <= n; ++ i) {
		scanf("%d", &v[i]);
	}

	for(int i = 1; i <= n; ++ i) {
		while(!dq.empty() && v[dq.back()] >= v[i]) {
			dq.pop_back();
		}
		dq.push_back(i);
		if(i - dq.front() + 1 > k)
			dq.pop_front();
		if(i >= k && sol < v[dq.front()]) {
			sol = v[dq.front()];
			is = i - k + 1;
			js = i;
		}
	}

	printf("%d %d %d\n", is, js, sol);

	return 0;
}