Cod sursa(job #634207)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 15 noiembrie 2011 20:20:45
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 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;

#define D 8192
char g_buf[D];
int g_p=D-1;


inline int get()
{

	int x=0,neg;
	while ((g_buf[g_p]<'0' || g_buf[g_p]>'9') && g_buf[g_p]!='-')
		if (++g_p==D) fread(g_buf,1,D,stdin),g_p=0;
	neg=0;
	if(g_buf[g_p]=='-'){	neg=1;
		if(++g_p==D) fread(g_buf,1,D,stdin),g_p=0;
	}
	while (g_buf[g_p]>='0' && g_buf[g_p]<='9'){
		x=x*10+g_buf[g_p]-'0';
		if (++g_p==D) fread(g_buf,1,D,stdin),g_p=0;
	}
	if (neg) x=-x;
	return x;
}

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	//scanf("%d %d", &N, &K);
	N=get();
	K=get();
	
	for (i=1;i<=N;++i)
		 //scanf("%d", &V[i]);
	     V[i]=get();
	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;
	
}