Cod sursa(job #2217095)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 29 iunie 2018 01:13:25
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5;
const int MAXK = 5e5;

int n, k, nr;
deque<pair<int, int>> dq;
int maxim = -30001;
int st, dr;

int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;

	for (int i = 1; i < k; ++ i) {
		cin >> nr;
		while (dq.size() && dq.back().first >= nr) dq.pop_back();
		dq.push_back({nr, i});
	}

	for (int i = k; i <= n; ++ i) {
		cin >> nr;
		while (dq.size() && dq.front().second <= i - k) dq.pop_front();
		while (dq.size() && dq.back().first >= nr) dq.pop_back();
		dq.push_back({nr, i});
		if (dq.front().first > maxim) {
			st = i - k + 1;
			dr = i;
			maxim = dq.front().first;
		}

	}

	cout << st << ' ' << dr << ' ' << maxim;


	return 0;
}