Cod sursa(job #2656324)

Utilizator marquiswarrenMajor Marquis Warren marquiswarren Data 7 octombrie 2020 14:34:02
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <deque>
#include <cctype>

const int NMAX = 500005;
const int BUFFMAX = 7000000;
int n, k, a[NMAX];

char buff[BUFFMAX];

void scan(int& x) {
	static int i = 0;

	if (i == 0) {
		fread(buff, 1, BUFFMAX, stdin);
	}

	while (!isdigit(buff[i]) && buff[i] != '-')
		i++;

	int sign = buff[i] == '-' ? -1 : 1;
	if (sign == -1) i++;

	int num = 0;

	while (isdigit(buff[i]))
		num = num * 10 + buff[i++] - '0';

	x = sign * num;
}

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

	scan(n);
	scan(k);
	for (int i = 1; i <= n; i++)
		scan(a[i]);

	std::deque<int> d;

	int base_max = -50000;
	std::pair<int, int> range;

	for (int i = 1; i <= n; i++) {
		if (d.front() == i - k)
			d.pop_front();

		while (!d.empty() && a[d.back()] >= a[i])
			d.pop_back();

		d.push_back(i);

		while (!d.empty() && d.front() <= i - k)
			d.pop_front();

		if (i >= k && a[d.front()] > base_max) {
			base_max = a[d.front()];
			range = {d.front(), d.back()};
			range = {i - k + 1, i};
		}
	}

	printf("%d %d %d\n", range.first, range.second, base_max);

	return 0;
}