Cod sursa(job #460399)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 2 iunie 2010 14:40:06
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <stdio.h>
#define DIM 500002
#define INF 2000000001

int A[DIM], Deque[DIM];
int N, K, Bmin, Bpoz;

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

	int i, p, u;
	
	scanf ("%d %d", &N, &K);
	for (i=1; i<=N; i++) scanf ("%d", &A[i]);
	
	p = 1, u = 0, Bmin = -INF;
	for (i=1; i<=N; i++){
		while (p <= u && A[i] <= A[Deque[u]])
			u--;
		Deque[++u] = i;
		if (Deque[p] == i-K)
			p++;
		if (i >= K)
			if (Bmin < A[Deque[p]])
				Bmin = A[Deque[p]], Bpoz = i;		
	}
	
	printf ("%d %d %d\n", Bpoz-K+1, Bpoz, Bmin);
	
	return 0;
}