Cod sursa(job #74552)

Utilizator slayer4uVictor Popescu slayer4u Data 26 iulie 2007 10:12:03
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
#include<stdio.h>
int i,n,dq[500001],k,x[500001],inc,sf,msf,minc,max=-2147000000;
int main()
{
	freopen ("secventa.in","rt",stdin);
	freopen ("secventa.out","wt",stdout);

	scanf("%ld %ld",&n,&k);
	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);

	inc=1;sf=0;
	for (i=1;i<=n;i++)
	{
		while (sf>=inc && x[dq[sf]]>=x[i])
			sf--;
		dq[++sf]=i;

		if (i-dq[inc]>=k)
			inc++;
		if (x[dq[inc]]>max && i>=k)
		{
			max=x[dq[inc]];
			msf=i;
			minc=i-k+1;
		}
	}
	
	printf("%ld %ld %ld\n",minc,msf,max);
	return 0;
}