Cod sursa(job #2877835)

Utilizator livliviLivia Magureanu livlivi Data 25 martie 2022 14:06:50
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

int main() {
	int n, k; cin >> n >> k;
	vector<int> v(n);

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	deque<pair<int, int>> deq;
	for (int i = 0; i < k; i++) {
		while (!deq.empty() && deq.back().first >= v[i]) {
			deq.pop_back();
		}
		deq.push_back({v[i], i});
	}

	int st = 0, dr = k - 1, max = deq.front().first;
	for (int i = k; i < n; i++) {
		if (deq.front().second == i - k) {
			deq.pop_front();
		}
		while (!deq.empty() && deq.back().first >= v[i]) {
			deq.pop_back();
		}
		deq.push_back({v[i], i});

		if (deq.front().first > max) {
			max = deq.front().first;
			dr = i;
			st = i - k + 1;
		}
	}

	cout << st + 1 << " " << dr + 1 << " " << max << "\n";
	return 0;
}