Cod sursa(job #152421)

Utilizator savimSerban Andrei Stan savim Data 9 martie 2008 14:10:55
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <stdio.h>
#define maxl 100010

int o,t,i,j,k,n,x,l,max;
int d[maxl],a[maxl],b[maxl][2];
int heap[maxl];
long long sum=0;
void inter(int p, int q)
{
	 int r=(p+q)/2,i,x=p,y=r+1;
	 k=0;
	 while (x<=r && y<=q)
	 {
		k++;
		if (d[x]<d[y]) {b[k][0]=d[x];b[k][1]=a[x];x++;}
		else {b[k][0]=d[y];b[k][1]=a[y];y++;}
	 }
	 while (x<=r) {k++;b[k][0]=d[x];b[k][1]=a[x];x++;}
	 while (y<=q) {k++;b[k][0]=d[y];b[k][1]=a[y];y++;}
	 k=0;
	 for (i=p; i<=q; i++) {k++;d[i]=b[k][0];a[i]=b[k][1];}
}
void merge(int p, int q)
{
	int r=(p+q)/2;
	if (p==q) return;
	merge(p,r);
	merge(r+1,q);
	inter(p,q);
	if (p>=q) return;
}
int main()
{
	freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    
    scanf("%d %d %d",&n,&x,&l);
    for (i=1; i<=n; i++)
        scanf("%d %d",&d[i],&a[i]);
    
    max=0;
	for (i=1; i<=n; i++)
		if (d[i]>x) d[i]=-1;
		else
		{
			d[i]=(x-d[i])/l+1;
			if (d[i]>max) max=d[i];
		}
	merge(1,n);
	k=0;l=0;
	d[0]=0;
	j=n;
	for (i=max; i>=1; i--)
	{
		 while (j>0 && d[j]==i)
		 {
            k++;
            heap[k]=a[j];
            x=k;
            while (x/2>0)
            {
				if (heap[x/2]<heap[x]) {t=heap[x/2];heap[x/2]=heap[x];heap[x]=t;}
				else break;
				x/=2;
            }
            j--;
        }
		if (k==0) heap[1]=0;

		sum+=heap[1];
		// eliminare pozitia 1 din heap

		heap[1]=heap[k];k--;
		x=1;
		if (k>0)
		while (x*2<=k)
		{
			int p=2*x,q=2*x;
			if (2*x+1<=k) q++;
			if (heap[x]<heap[p] || heap[x]<heap[q])
			{
				if (heap[p]>=heap[q])
				{
					t=heap[x];
					heap[x]=heap[p];
					heap[p]=t;
					x=p;
				}
				else {
						t=heap[x];
						heap[x]=heap[q];
						heap[q]=t;
						x=q;
					 }
			}
			else break;
		}
	}
	printf("%lld\n",sum);
	return 0;
}