Cod sursa(job #806881)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 3 noiembrie 2012 17:57:05
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include<stdio.h>

#define Nmax 500001

int V[Nmax], Deque[Nmax], N, k, st, dr, poz, min;

int main() {
	
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	
	int i;
	
	scanf("%d %d",&N,&k);
	
	scanf("%d",&V[1]);
	st = dr = 1;
	Deque[st] = 1;
	min = -1<<30;
	
	for(i=2; i<=N; i++) {
		scanf("%d",&V[i]);
		
		while(V[i] <= V[Deque[dr]] && st<=dr)
			dr--;
		// sterg din deque toate elem mai mari ca V[i] formand mereu in felul asta un sir crescator in deque
		
		Deque[++dr] = i;
		// adaug pozitia elementului curent
		
		while(Deque[st]+k <= i)
			st++;
		
		if(min < V[Deque[st]] && i>=k) {
			min = V[Deque[st]];
			poz = i;
		}
	}
	
	printf("%d %d %d\n",poz-k+1,poz,min);
	
	return 0;
}