Cod sursa(job #1697957)

Utilizator quochuyaNguyen Quoc Huy quochuya Data 3 mai 2016 13:00:08
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

const int maxN = (int)5E5;

int a[maxN], dq[maxN];

void Solve() {
	int n, k;
	// scanf("%d %d", &n, &k);
	cin >> n >> k;

	int r, m, top, bot;
	m = -(int)2E9;

	top = -1; bot = 0;
	for(int i = 0; i < n; ++i) {
		// scanf("%d", &a[i]);
		cin >> a[i];
		while (top >= bot && a[i] < a[dq[top]]) --top;
		dq[++top] = i;
		if (i >= k-1) {
			while (top >= bot && dq[bot] < i-k+1) ++bot;
			if (a[dq[bot]] > m)
				m = a[dq[bot]], r = i;
		}
	}

	cout << r-k+2 << " " << r+1 << " " << m << "\n";
	// printf("%d %d %d\n", r-k+2, r+1, m);
}

int main() {
	ios_base::sync_with_stdio(false);
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	Solve();
	return 0;
}