Pagini recente » Cod sursa (job #1174932) | Cod sursa (job #3131949) | Cod sursa (job #125026) | Cod sursa (job #2070157) | Cod sursa (job #196260)
Cod sursa(job #196260)
#include <cstdio>
#include <algorithm>
#define N_MAX 1<<17
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN "lupu.in"
#define OUT "lupu.out"
using namespace std;
long long T_MAX,N,X,L;
struct oaie{long long t,l;};
oaie V[N_MAX];
long long H[N_MAX];
long long suma;
inline int father(int nod) {return nod / 2; }
inline int left_son(int nod) {return nod * 2; }
inline int right_son(int nod) {return nod * 2 + 1;}
void scan()
{
int x;
freopen(IN, "r",stdin);
freopen(OUT, "w",stdout);
scanf("%lld%lld%lld", &N,&X,&L);
FOR(i,1,N)
{
scanf("%lld%lld",&x,&V[i].l);
V[i].t=(X-x)/L;
if(V[i].t>T_MAX)
T_MAX=V[i].t;
}
}
void percolate(long long N, long long K)
{
int key = H[K];
while ((K > 1) && (key > H[father(K)]))
{
H[K] = H[father(K)];
K = father(K);
}
H[K] = key;
}
void sift(long long N, long long K)
{
int son;
do
{
son = 0;
if (left_son(K) <= N)
{
son = left_son(K);
if (right_son(K) <= N && H[right_son(K)] > H[left_son(K)])
{
son = right_son(K);
}
if (H[son] <= H[K])
{
son = 0;
}
}
if (son)
{
swap(H[K], H[son]);
K = son;
}
} while (son);
}
void cut(long long N, long long K)
{
H[K] = H[N];
--N;
if ((K > 1) && (H[K] > H[father(K)]))
{
percolate(N, K);
}
else
{
sift(N, K);
}
}
void insert(long long N, long long key)
{
H[N] = key;
percolate(N, N);
}
inline int comp (const oaie &x, const oaie &y)
{
if(x.t<y.t)
return 0;
return 1;
}
void solve()
{
sort(V+1,V+N+1, comp);
V[N+1].t=V[N].t-1;
int last=0;
FOR(i,1,N)
{
insert(++last,V[i].l);
if(V[i].t!=V[i+1].t)
FOR(k,1,(V[i].t-V[i+1].t))
{
if(!last)
break;
suma+=H[1];
cut(last,1);
--last;
}
}
printf("%lld\n",suma);
}
int main()
{
scan();
solve();
return 0;
}