Cod sursa(job #155560)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 12 martie 2008 00:02:16
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.49 kb
#include<stdio.h>
#define nmax 500000
int v[nmax],w[nmax];
int main()
{
	int  rez,i,j,n,k,val,min,s,in,sf;
	min=-nmax; in=0;
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d %d",&n,&k);
	sf=-1;
	for(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;
		}

	}
	rez=s-k+1;
	printf("%d %d %d\n",rez,s,min);
	return 0;
}