Pagini recente » Cod sursa (job #1053166) | Cod sursa (job #1734396) | Cod sursa (job #2939908) | Cod sursa (job #2398176) | Cod sursa (job #331550)
Cod sursa(job #331550)
#include <algorithm>
#define DIM 100005
using namespace std;
struct nod {int x;
nod *urm;} *lst[DIM];
int h[DIM],d[DIM],a[DIM];
int n,x,l,m,nrt,tmax,p;
void read ()
{
int i,nr;
scanf ("%d%d%d",&n,&x,&l);
for (i=1; i<=n; ++i)
{
scanf ("%d%d",&nr,&a[i]);
if (nr<=x)
h[i]=d[i]=(x-nr)/l+1;
}
}
int cbin (int val)
{
int st,dr,mij,sol=0;
for (st=1, dr=p; st<=dr; )
{
mij=(st+dr)/2;
if (h[mij]==val)
sol=mij;
if (h[mij]<val)
st=mij+1;
else
dr=mij-1;
}
return sol;
}
void norm ()
{
int i;
sort (h+1,h+n+1);
for (i=p=1; i<=n; ++i)
if (h[i]!=h[p])
h[++p]=h[i];
for (i=1; i<=n; ++i)
if (d[i])
{
d[i]=cbin (d[i]);
if (d[i]>tmax)
tmax=d[i];
}
}
void add (int a,int b)
{
nod *p=new nod;
p->x=b;
p->urm=lst[a];
lst[a]=p;
}
void init ()
{
int i;
for (i=1; i<=n; ++i)
if (d[i])
add (d[i],a[i]);
}
void swap (int &a,int &b)
{
int aux=a;
a=b;
b=aux;
}
void upheap (int nod)
{
for (; nod>1 && h[nod]>h[nod/2]; nod/=2)
swap (h[nod],h[nod/2]);
}
void downheap (int nod)
{
int son;
do
{
son=0;
if (2*nod<=m)
{
son=2*nod;
if (2*nod+1<=m && h[2*nod+1]>h[2*nod])
son=2*nod+1;
if (h[son]<=h[nod])
son=0;
}
if (son)
{
swap (h[nod],h[son]);
nod=son;
}
}
while (son);
}
void solve ()
{
nod *p;
int i;
for (i=tmax; i>=1; --i)
{
for (p=lst[i]; p; p=p->urm)
{
h[++m]=p->x;
upheap (m);
}
if (m)
{
nrt+=h[1];
h[1]=h[m--];
downheap (1);
}
}
printf ("%d",nrt);
}
int main ()
{
freopen ("lupu.in","r",stdin);
freopen ("lupu.out","w",stdout);
read ();
norm ();
init ();
solve ();
return 0;
}