Pagini recente » Cod sursa (job #2442603) | Cod sursa (job #2953183) | Cod sursa (job #1361572) | Cod sursa (job #329896) | Cod sursa (job #325792)
Cod sursa(job #325792)
#include<stdio.h>
#include<stdlib.h>
#define NM 100005
struct bee{int d,a,g;};
typedef bee*pb;
bee v[NM];
struct oaie{int d,a;};
oaie h[NM];
int n,n1,idgr;
inline int tata(int k){return k/2;}
inline int fiu_st(int k){return k*2;}
inline int fiu_dr(int k){return k*2+1;}
inline int max(){return h[1].a;}
void sift(int k){
int fiu;
oaie aux;
do{
fiu=0;
if(fiu_st(k)<=n) fiu=fiu_st(k);
if(fiu_dr(k)<=n&&h[fiu_dr(k)].a>h[fiu_st(k)].a)
fiu=fiu_dr(k);
if(h[fiu].a<=h[k].a) fiu=0;
if(fiu) aux=h[k],h[k]=h[fiu],h[fiu]=aux,k=fiu;
}while(fiu);
}
void percolate(int k){
oaie temp=h[k];
while(k>1&&temp.a>h[tata(k)].a) h[k]=h[tata(k)],k=tata(k);
h[k]=temp;
}
void insert(bee x){
++n;
h[n].d=x.d,h[n].a=x.a;
percolate(n);
}
void clear(int k){
h[k]=h[n--];
if(n)
if(k>1&&h[k].a>h[tata(k)].a) percolate(k);
else sift(k);
}
/*
void build_heap(){
int i;
for(i=n/2;i;--i) sift(i);
} */
int fcmp(void const*e,void const*f){
return ((pb)e)->g-((pb)f)->g;
}
int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int i,j,m,x,l,d,a,c,r,grmax,dif;
scanf("%d%d%d",&m,&x,&l);
c=x/l,r=x%l;
if(r) grmax=(x+r)/l;
else grmax=(x+l-1)/l;
for(i=1;i<=m;++i){
scanf("%d%d",&d,&a);
if(h[i].d<=x)
{
v[n1].d=d,v[n1].a=a;
if(r) v[n1].g=(v[n1].d+r)/l;
else v[n1].g=(v[n1].d+l-1)/l;
++n1;
}
}
qsort(v,n1,sizeof(v[0]),fcmp);
int init=v[0].g;
long long s=0L;
for(i=0;i<n1;++i){
idgr=v[i].g;
j=i;
while(j<n1&&v[j].g==idgr) insert(v[j]),j++;
if(j<=n1-1){
dif=v[j].g-idgr+init;
}
else dif=grmax-v[n1-1].g+1;
while(n&&dif) s+=h[1].a,clear(1),dif--;
if(j==n1) break;
i=j-1;
}
printf("%lld",s);
return 0;
}