Cod sursa(job #2891438)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 18 aprilie 2022 18:05:34
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <deque>
#include <fstream>

#define NMAX 500005
#define MAX 30005

using namespace std;

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

int v[NMAX];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> v[i];

	deque <int> dq;
	for (int i = 1; i <= k; ++i) {
		while (!dq.empty() && v[dq.back()] >= v[i])
			dq.pop_back();
		dq.push_back(i);
	}

	int best = v[dq.front()];
	int best_start = 1;
	int best_end = k;

	for (int i = k + 1; i <= n; ++i) {
		while (!dq.empty() && v[dq.back()] >= v[i])
			dq.pop_back();
		dq.push_back(i);
		if (i - dq.front() + 1 > k)
			dq.pop_front();
		if (best < v[dq.front()]) {
			best = v[dq.front()];
			best_start = i - k + 1;
			best_end = i;
		}
	}

	while (best_start >= 2 && v[best_start - 1] >= best)
		--best_start;

	cout << best_start << ' ' << best_end << ' ' << best << '\n';
	return 0;
}