Cod sursa(job #129792)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 30 ianuarie 2008 11:11:45
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <ctype.h>

#define MAXN 500010

long a[MAXN], n, k;
char st[MAXN * 7];
long deq[MAXN], start, final;

inline void insert(long value) {
	while (final >= start && deq[final] > value) {
		--final;
	}
	deq[++final] = value;
}

inline void del(long value) {
	if (deq[start] == value) {
		++start;
	}
}

int main() {
	long i, na, p = 0, ok = 0, semn = 1, max = 0, poz_st = 0;
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	scanf("%ld %ld\n", &n, &k);
	fgets(st, MAXN * 7, stdin);
	na = 0;
	for (i = 0; st[i] != 0; ++i) {
		if (st[i] == '-') {
			semn = -1;
			continue;
		}
		if (isdigit(st[i])) {
			p = p * 10 + (long)(st[i] - '0');
			ok = 1;
		} else {
			a[++na] = p * semn;
			p = 0;
			semn = 1;
			ok = 0;
		}
	}
	if (ok) {
		a[++na] = p;
		p = 0;
	}
	
	//deque
	for (i = 1; i <= k; ++i) {
		insert(a[i]);
	}
	
	max = deq[start];
	poz_st = 1;
	
	for (i = k + 1; i <= n; ++i) {
		del(a[i - k]);
		insert(a[i]);
		if (max < deq[start]) {
			max = deq[start];
			poz_st = i - k + 1;
		}
	}
	printf("%ld %ld %ld\n", poz_st, poz_st + k - 1, max);
	return 0;
}