Pagini recente » Cod sursa (job #532846) | Cod sursa (job #721609) | Cod sursa (job #129330) | Cod sursa (job #2854456) | Cod sursa (job #347130)
Cod sursa(job #347130)
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct che{long d,l,r;}a[600010];
long n,l,i,lh,ru,x,hh,h[600010];
long long lna;
long cmp(che a,che b)
{if(a.r>b.r)return 1;
return 0;}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%ld%ld%ld",&n,&x,&l);
for(i=1;i<=n;++i)
{scanf("%ld%ld",&a[i].d,&a[i].l);
a[i].r=(x-a[i].d)/l+1;
if(x<a[i].d){--i;--n;}}
sort(a+1,a+n+1,cmp);
lh=0;
lna=0;
ru=a[1].r;
for(i=1;i<=n;++i)
{if(a[i].r==ru)
{++lh;
h[lh]=i;
x=lh;
while(a[h[x]].l>a[h[x/2]].l&&x>1){hh=h[x];h[x]=h[x/2];h[x/2]=hh;x/=2;}}
while(a[i+1].r!=ru)
{if(lh==0){ru=a[i+1].r;break;}
ru--;
lna+=a[h[1]].l;
h[1]=h[lh--];
if(lh)
{x=1;
while(a[h[x]].l<a[h[2*x]].l||a[h[x]].l<a[h[2*x+1]].l)
if(a[h[2*x]].l>a[h[2*x+1]].l){swap(h[2 * x],h[x]);x*=2;}
else {swap(h[2 * x + 1],h[x]);x=x*2+1;}}}}
printf("%lld\n",lna);
return 0;
}