Cod sursa(job #1697904)

Utilizator quochuyaNguyen Quoc Huy quochuya Data 3 mai 2016 10:05:24
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

const int maxN = (int)5E3;

int n, k, l, r, m;
int a[maxN];
deque<int> dq;

int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	scanf("%d %d", &n, &k);
	for(int i = 0; i < n; ++i)
		scanf("%d", &a[i]);
	dq.clear();

	m = -(int)2E9;

	for(int i = 0; i < n; ++i) {
		while (!dq.empty() && a[i] <= a[dq.back()]) dq.pop_back();
		dq.push_back(i);
		while (!dq.empty() && dq.front() < i-k+1) dq.pop_front();
		if (i >= k-1 && a[dq.front()] > m) {
			m = a[dq.front()];
			l = i-k+1;
			r = i;
		}
	}

	printf("%d %d %d\n", l+1, r+1, m);
	return 0;
}