Pagini recente » Cod sursa (job #2943857) | Cod sursa (job #50747) | Cod sursa (job #823673) | Cod sursa (job #1130088) | Cod sursa (job #146351)
Cod sursa(job #146351)
#include <stdio.h>
#define maxl 100010
int o,t,i,j,k,n,x,l;
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 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;l=0;
int timp=-1;
d[0]=0;
if (d[1]==0) o=-1;
for (i=n; i>=1; i--)
if (d[i]!=timp && d[i]>=0)
{
for (j=i; j>=0; j--)
if (d[j]==d[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;}
x/=2;
}
}
else {o=d[j];break;}
if (o==-1) {l=1; o=d[i]-1;}
if (o==d[i]) o=d[i]-1;
for (j=o+1; j<=d[i]; j++)
{
sum+=heap[1];
// eliminare pozitia 1 din heap
if (k==1) break;
t=heap[1];heap[1]=heap[k];heap[k]=t;k--;
x=1;
int xant;
while (x*2<=k)
{
int p=2*x,q=2*x;
xant=x;
if (2*x+1<=k) q++;
if (heap[p]>heap[q])
{
t=heap[x];
heap[x]=heap[p];
heap[p]=t;
x=p;
}
else if (q>p)
{
t=heap[x];
heap[x]=heap[q];
heap[q]=t;
x=q;
}
if (x==xant) break;
}
}
timp=d[i];
if (l) break;
}
printf("%lld\n",sum);
return 0;
}