Cod sursa(job #195506)

Utilizator AndreyPAndrei Poenaru AndreyP Data 19 iunie 2008 10:36:49
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>
int n,c,ka,min=30010;
int v[500010],a[500010];
inline int father(int x)
{
	return x>>1;
}
inline int left_son(int x)
{
	return x<<1;
}
inline int right_son(int x)
{
	return (x<<1)+1;
}
void upheap(int k)
{
	int key=v[k];
	while((k>1)&&(a[key]<a[v[father(k)]]))
	{
		v[k]=v[father(k)];
		k=father(k);
	}
	v[k]=key;
}
void downheap(int k)
{
	int son,aux;
	do
	{
		son=0;
		if(left_son(k)<=c)
			son=left_son(k);
		if((right_son(k)<=c)&&(a[v[son]]>a[v[right_son(k)]]))
			son=right_son(k);
		if(a[v[son]]>=a[v[k]])
			son=0;
		if(son)
		{
			aux=v[son];
			v[son]=v[k];
			v[k]=aux;
			k=son;
		}
	}while(son);
}
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d",&n,&ka);
	int i,poz;
	for(i=1; i<=n; i++)
		scanf("%d",&a[i]);
	/*for(c=1; c<=n; c++)
	{
		scanf("%d",&v[c]);
		upheap(c);
	}
	for(i=1; i<=n; i++)
		printf("%d ",v[i]);
	printf("\n");*/
	for(c=1; c<=ka; c++)
	{
		v[c]=c;
		upheap(c);
	}
	min=v[1];
	poz=1;
	c--;
	for(i=ka+1; i<=n; i++)
	{
		while(i-v[1]+1>ka)
		{
			v[1]=v[c];
			c--;
			downheap(1);
		}
		v[++c]=i;
		upheap(c);
		if(a[v[1]]>a[min]){
			min=v[1];
			poz=i-ka+1;
		}
	}
	printf("%d %d %d\n",poz,poz+ka-1,a[min]);
	return 0;
}