Cod sursa(job #2211091)

Utilizator memecoinMeme Coin memecoin Data 9 iunie 2018 13:12:04
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <deque>
#include <string.h>

using namespace std;

int n, k;

struct entry {
	int value;
	int index;
};

deque<entry> d;
int v[500025];
char s[4000005];

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

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

	int best = -0x3f3f3f3f;
	int bestOcc;

	gets(s);

	int nn = strlen(s);
	int i = 0;
	int semn;
	int nr = 0;
	int kk = 0;
	while (i<nn) {
		semn = 1;
		if (s[i] == '-') {
			semn = -1;
			++i;
		}
		while (i<nn && s[i] >= '0' && s[i] <= '9') {
			nr = nr * 10 + s[i] - '0';
			++i;
		}
		nr *= semn;
		v[kk] = nr;
		nr = 0;
		++i;
		++kk;
	}

	for (int i = 0; i < n; ++i) {
		int x = v[i];
		
		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;
}