Cod sursa(job #602154)

Utilizator anarogozAna Rogoz anarogoz Data 9 iulie 2011 13:25:21
Problema Lupul Urias si Rau Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
#include<stdlib.h>
struct oi
{
	long d,l;
};

oi o[100005];
long h[100004],u;
int cmp( const void *a,const void *b)
{
	oi *pa,*pb;
	pa=(oi*)a;
	pb=(oi*)b;
	if(pa->d==pb->d)
		return 0;
	if(pa->d<pb->d)
		return -1;
	return 1;
}

void down(int k)
{
	int fiu,aux;
	do
	{
		fiu=0;
		if(2*k<=u)
				fiu=2*k;
		if(2*k+1<=u&&h[2*k+1]>h[fiu])
				fiu=2*k+1;
		if(h[fiu]>h[k])
		{
			aux=h[fiu];
			h[fiu]=h[k];
			h[k]=aux;
			k=fiu;
		}
		else
			fiu=0;
	}while(fiu!=0);
}

void up(int k)
{
	int aux;
	while(k>1&&h[k]>h[k/2])
	{
		aux=h[k];
		h[k]=h[k/2];
		h[k/2]=aux;
		k=k/2;
	}
}

void insert(int k)
{
	h[++u]=k;
	up(u);
}

void stergere(int k)
{
	h[k]=h[u];
      u--;
	down(k);
}	

	
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	long n,i,dist=0,t=0,x,l,d;
	scanf("%ld%ld%ld",&n,&x,&l);
	for(i=1;i<=  n;i++)
		scanf("%ld%ld",&o[i].d,&o[i].l);
	qsort(o+1,n,sizeof(o[0]),cmp);
	i=1;
	for(dist=0;dist<=x&&i<=n;dist=dist+l)
	{
		for( ;i<=n&&o[i].d<=dist;i++)
			insert(o[i].l);
		t=t+h[1];
		stergere(1);
	}	
	printf("%ld\n",t);	
	return 0;
}