Cod sursa(job #251447)

Utilizator P1gl3TGilca Mircea Alexandru P1gl3T Data 2 februarie 2009 17:56:46
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>
const int N=500001;
int start,end,deque[N];
char buff[N*8],*c;
int read()
{
	int sgn=1,val=0;
	if(*c=='-'){ sgn=-1; ++c; }
	while(*c>='0'&&*c<='9')
	{
		val=val*10+*c-'0';
		++c;
	}
	++c;
	return val*sgn;
}
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	int v[N],deque[N],n,k;
	int i,l,max=-30001;
	scanf("%d%d\n",&n,&k);
	fgets(buff,8*N,stdin);
	c=buff;
	for(i=1;i<=n;++i)
		v[i]=read();
	start=1;
	end=0;
	for(i=1;i<=n;++i)
	{
		while(start<=end&&v[deque[end]]>=v[i]) --end;
		deque[++end]=i;
		if(deque[start]==i-k) ++start;
		if(v[deque[start]]>max&&i>=k)
		{
			max=v[deque[start]];
			l=i;
		}
	}
	printf("%d %d %d\n",l-k+1,l,max);
	return 0;
}