Pagini recente » Istoria paginii runda/simulareojiclasa7 | Cod sursa (job #2765853) | Cod sursa (job #2729856) | Istoria paginii runda/moisil2011/clasament | Cod sursa (job #542814)
Cod sursa(job #542814)
#include <cstdio>
#include <algorithm>
using namespace std;
struct nod
{long long d,l;} v[100002];
int q[100002];
int cmp(const nod &x,const nod &y)
{ return x.d<=y.d; }
int main()
{
int n,i,nr=0;
long long x,l,d=0,sol=0;
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d %lld %lld",&n,&x,&l);
for (i=1;i<=n;++i)
{
scanf("%lld %lld",&v[nr+1].d,&v[nr+1].l);
if (v[nr+1].d<=x) ++nr;
}
sort(v+1,v+nr+1,cmp);
for (i=1;i<=nr&&d<=x;d+=l)
{
while ((i<=n) && (v[i].d<=d))
{
++q[0];
int p=q[0];
while ((p>1) && (v[q[p/2]].l<v[i].l))
{
q[p]=q[p/2];
p/=2;
}
q[p]=i;
++i;
}
if (q[0])
{
sol+=v[q[1]].l;
--q[0];
int p=1;
while (p*2<=q[0])
{
int ok1,ok2=ok1=0;
ok1=v[q[p*2]].l;
if (p*2+1<=q[0]) ok2=v[q[p*2+1]].l;
if ((ok1>v[q[q[0]+1]].l) && (ok2>v[q[q[0]+1]].l))
{
if (ok1>ok2) q[p]=q[p*2],p*=2; else
q[p]=q[p*2+1],p=p*2+1;
} else
if (ok1>v[q[q[0]+1]].l)
q[p]=q[p*2],p*=2; else
if (ok2>v[q[q[0]+1]].l)
q[p]=q[p*2],p=p*2+1; else
break;
}
q[p]=q[q[0]+1];
}
}
printf("%lld",sol);
return 0;
}