Cod sursa(job #128995)

Utilizator blahblahblahblah blahblah Data 28 ianuarie 2008 14:10:46
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>

#define NMAX 500010

int N, K;

int deck[NMAX];
int poz[NMAX];

int main()
{
	int i;
	
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	
	scanf("%d %d", &N, &K);
	
	int p, q, mx = -30010, sol = 0, val;
	p = 0; q = -1;
	for (i = 1; i <= N; i++) {
		scanf("%d", &val);
		
		while (p <= q && poz[p] <= i - K) p++;
		
		while (p <= q && deck[q] > val) q--;
		q++;
		deck[q] = val;
		poz[q] = i;
		
		if (i >= K && deck[p] > mx) {
			mx = deck[p];
			sol = i;
		}
	}
	
	printf("%d %d %d\n", sol - K + 1, sol, mx);
	
return 0;
}