Cod sursa(job #2891447)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 18 aprilie 2022 18:23:36
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <deque>
#include <stdio.h>

#define NMAX 500001
#define MAX 30001

using namespace std;

short int v[NMAX];

int main()
{
	FILE *in, *out;
	in = fopen("secventa.in", "rt");
	out = fopen("secventa.out", "wt");

	int n, k;
	fscanf(in, "%d %d", &n, &k);

	deque <int> dq;
	for (int i = 1; i <= k; ++i) {
		fscanf(in, "%hd", v + 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) {
		fscanf(in, "%hd", v + 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();
		int dq_fr = dq.front();
		if (best < v[dq_fr]) {
			best = v[dq_fr];
			best_start = i - k + 1;
			best_end = i;
		}
	}

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

	fprintf(out, "%d %d %d\n", best_start, best_end, best);

	fclose(in);
	fclose(out);
	return 0;
}