Cod sursa(job #195507)

Utilizator AndreyPAndrei Poenaru AndreyP Data 19 iunie 2008 10:44:12
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<stdio.h>
int n,c,ka,min=30010;
int v[500010],a[500010];
char p[3500010];
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);
}
void citeste()
{
	int i,semn=1,aux=0,k=0;
	fgets(p,3500010,stdin);
	for(i=0; p[i]!='\0'; i++)
	{
		if((p[i]<='9')&&(p[i]>='0'))
			aux=aux*10+p[i]-'0';
		else
		if(p[i]=='-')
			semn=-1;
		else
		{
			a[++k]=aux*semn;
			aux=0;
			semn=1;
		}
	}
}
int main()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d\n",&n,&ka);
	int i,poz;
	citeste();
	//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;
}