Cod sursa(job #2211073)

Utilizator memecoinMeme Coin memecoin Data 9 iunie 2018 12:48:24
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <deque> 

using namespace std;

int n, k;

struct entry {
	int value;
	int index;
};

deque<entry> d;

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

	scanf("%d %d", &n, &k);

	int best = -0x3f3f3f3f;
	int bestOcc;

	for (int i = 0; i < n; ++i) {
		int x;
		scanf("%d", &x);
		
		while (!d.empty() && d.back().value >= x) {
			d.pop_back();
		}
		if (!d.empty() && d.front().index <= i - k) {
			d.pop_front();
		}
		d.push_back({ x, i });

		if (i >= k - 1 && d.front().value > best) {
			best = d.front().value;
			bestOcc = i - k + 1;
		}
	}

	printf("%d %d %d", bestOcc + 1, bestOcc + k, best);

	return 0;
}