Cod sursa(job #158746)

Utilizator mariussMarius Telespan mariuss Data 13 martie 2008 20:06:31
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.5 kb
#include<stdio.h>
#define nmax 500000
int i,j,n,k,val,min=-nmax,s,in,sf,v[nmax],w[nmax];
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);

	scanf("%d %d",&n,&k);
	in=0;
	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;
		}

	}

	printf("%d %d %d\n",s-k+1,s,min);

	return 0;
}