Cod sursa(job #634205)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 15 noiembrie 2011 20:18:17
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>

#define file_in "secventa.in"
#define file_out "secventa.out"

#define nmax 501010

int N,K,V[nmax];
int front,back,val;
int deque[nmax];
int inc,sf,i;

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &K);
	
	for (i=1;i<=N;++i)
		 scanf("%d", &V[i]);
	
	front=1;
	back=0;
	val=-0x3f3f3f3f;
	for (i=1;i<=N;++i){
		
		 while(front<=back && V[i]<=V[deque[back]]) back--;
		 deque[++back]=i;
		 if (deque[front]==i-K) front++;
		 if (i>=K && V[deque[front]]>val)
		 {
			 inc=i-K+1;
			 val=V[deque[front]];
			 sf=i;
		 }
	}
	
	printf("%d %d %d",  inc,sf, val);
	
	return 0;
	
}