Cod sursa(job #164633)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 24 martie 2008 16:47:34
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.45 kb
#include<stdio.h>
#define nmax 500000
int v[nmax],w[nmax];
int  n,k,val,min=-nmax,s,in=0,sf=-1;
int main()
{
	freopen("secventa.in", "r",stdin);
	freopen("secventa.out", "w",stdout);
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;++i)
	{
		scanf("%d", &val);
		while(in<=sf && w[in]<=i-k)
			++in;
		while(in<=sf && v[sf]>val)
			--sf; 	++sf;
		v[sf]=val; w[sf]=i;
		if(i>=k && v[in]>min)
		{min=v[in]; s=i;}
	}
	printf("%d %d %d\n",s-k+1,s,min);
	return 0;
}