Cod sursa(job #2217093)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 29 iunie 2018 01:08:25
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream in("secventa.in");
ofstream out("secventa.out");

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() {
	in >> n >> k;

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

	for (int i = k; i <= n; ++ i) {
		in >> nr;
		while (dq.front().second <= i - k) dq.pop_front();
		while (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;
		}

	}

	out << st << ' ' << dr << ' ' << maxim;


	return 0;
}