Cod sursa(job #1370586)

Utilizator PikachuPikachu Pikachu Data 3 martie 2015 15:56:33
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <cstring>
#include <deque>

using namespace std;

const int NMAX = 500000;

int v[NMAX + 5];
char s[8 * NMAX + 5];
deque <int> dq;

void read(int n) {
	int m, p = 1, nr = 0;
	bool minus = 0;

	gets(s);
	m = strlen(s);
	s[m] = ' ';

	for(int i = 0; s[i]; ++ i) {
		if(s[i] == ' ') {
			if(minus)
				nr = -nr;
			v[p] = nr;
			++ p;
			nr = 0;
			minus = 0;
		} else
		if(s[i] == '-') {
			minus = 1;
		} else {
			nr = nr * 10 + (s[i] - '0');
		}
	}
}

int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	int n, k, sol = -2000000000, is, js;

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

	read(n);

	for(int i = 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(i >= k && sol < v[dq.front()]) {
			sol = v[dq.front()];
			is = i - k + 1;
			js = i;
		}
	}

	printf("%d %d %d\n", is, js, sol);

	return 0;
}