Cod sursa(job #1169893)

Utilizator ThomasFMI Suditu Thomas Thomas Data 12 aprilie 2014 12:18:08
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h>
#include <math.h>

long n, k, i, first, last, max, p1, p2, x, nr, t;
char s[2500010];

struct deque{
	int v, i;
};

deque q[500005];

int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "wt", stdout);
	
	scanf("%ld%ld\n", &n, &k);
	fgets(s, 2500000, stdin); 
	nr = 0;
	if (s[nr] == '-') {
		nr++;
		t = 1;
	}
	for (; s[nr] >= '0' && s[nr] <= '9'; ++nr)
		x = x * 10 + s[nr] - '0';
	if (t == 1) {
		t = 0;
		x = -x;
	}
	q[1].v = x;
	q[1].i = 1;
	first = 1;
	last = 1;
	max = -30001;
	for (i = 2; i <= n; ++i){
		x = 0;
		++nr;
		if (s[nr] == '-'){
			++nr;
			t = 1;
		}
		for (; s[nr] >= '0' && s[nr] <= '9'; ++nr)
			x = x * 10 + (s[nr] - '0');
		if (t == 1) {
			t = 0;
			x = -x;
		}
		while (first <= last && i - q[first].i >= k)
			++first;
		while (first <= last && x <= q[last].v)
			--last;
		q[++last].v = x;
		q[last].i = i;
		if (q[first].v > max && i - k + 1 > 0){
			max = q[first].v;
			p1 = i - k + 1;
			p2 = i;
		}
	}
	printf("%ld %ld %ld\n", p1, p2, max);
	return 0;
}