Cod sursa(job #146340)

Utilizator savimSerban Andrei Stan savim Data 1 martie 2008 16:11:36
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <stdio.h>
#define maxl 100010
int o,t,i,j,k,n,x,l,xant;
int d[maxl],a[maxl],b[maxl][2];
int h[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 inter2(int p, int q)
{
	 int r=(p+q)/2,i,x=p,y=r+1;
	 k=0;
	 while (x<=r && y<=q)
	 {
		k++;
		if (a[x]<a[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]);

	for (i=1; i<=n; i++) 
     if (d[i]>x) d[i]=-1;     
	 else d[i]=(x-d[i])/l;

	merge(1,n);

	k=0;
	int timp=-1;

	if (d[1]==0) d[0]=-1;
	else d[0]=0;

	for (i=n; i>=1; i--)
		if (d[i]!=timp && d[i]>=0)
		{
		   for (j=i; j>=1; j--)
		   if (d[j]==d[i])
		   {
			  k++;
			  h[k]=a[j];
			  x=k;
			  while (x/2>0)
			  {
				  if (h[x/2]<h[x]) {t=h[x/2];h[x/2]=h[x];h[x]=t;}
				  x/=2;
			  }
		   }
		   else {o=d[j];break;}

           if (d[i]==-1) break;
		   if (o==d[i]) o=d[0];

		   for (j=o+1; j<=d[i]; j++)
		   {
				sum+=h[1];
				//eliminare pozitia 1 din heap

                if (k==1) break;
				x=h[1];h[1]=h[k];h[k]=x;k--;
				while (x*2<=k)
				{
					xant=x;
					if (h[x*2]>h[x]) {t=h[x*2];h[x*2]=h[x];h[x]=t;x*=2;}
					if (h[x*2+1]>h[x]) {t=h[x*2+1];h[x*2+1]=h[x];h[x]=t;x=x*2+1;}
					if (x==xant) break;
				}
		   }
           
           timp=d[i];  
	    }
	printf("%lld\n",sum);
	return 0;
}