Pagini recente » Cod sursa (job #3153774) | Cod sursa (job #2337184) | Cod sursa (job #2762585) | Cod sursa (job #2840646) | Cod sursa (job #2709140)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("lupu.in");
ofstream g ("lupu.out");
int const N = 1e5 + 3 , inf = (int)((1LL << 31) - 1);
int n , x , D ;
typedef long long ll;
struct oi {
int t , l;
bool operator < (oi r) const{
return t < r . t;
}
}A [N];
class Heap {
private :
int v [N] , h [N] , p [N] , in , k;
public:
int sz (){
return k;
}
int top (){
return v [h [1]];
}
void chg (int x , int y){
swap (h [x] , h [y]);
p [h [x]] = x , p [h [y]] = y;
}
void up (int n){
while (n > 1 && v [n] >= v [n / 2]){
chg (n , n / 2);
n >>= 1;
}
return;
}
void down (int n){
int nxt;
while (n * 2 <= k){
nxt = n;
if (2 * n <= k && v [h [nxt]] < v [h [n << 1]])
nxt = n << 1;
if (2 * n + 1 <= k && v [h [nxt]] < v [h [2 * n + 1]])
nxt = 2 * n + 1;
if (n == nxt){
n = 1 + k;
continue;
}
chg (n , nxt);
n = nxt;
}
return;
}
void pop (){
chg (1 , k --);
if (k)
down (1);
}
void push (int x){
v [++ in] = x;
h [++ k] = in;
p [in] = k;
up (k);
}
void clear (){
for(int i = 1 ; i <= k ; ++ i , -- k , pop ())
-- k;
}
} H;
inline int log2 (int x){
int i;
for(i = 0 ; (1 << i) <= x ; ++ i);
return i;
}
int bsearch (int from , int to , int x){
int pas (1 << log2 (to)) , r (from);
while (pas){
if (pas + r <= to && A [pas + r] . t <= x)
r += pas;
pas >>= 1;
}
return r;
}
ll solve (){
sort (A + 1 , A + 1 + n);
bool p = true ;
int i = 0 , j = 0;
ll r = 0;
while (p){
if (j > x){
p = false;
continue;
}
int pos = bsearch (i , n , j);
if (pos == i - 1 && H . sz ()){
r += H . top ();
continue;
}
else
for(; i <= pos ; ++ i)
H . push (A [i] . l);
r += H . top ();
j += D;
}
return r;
}
int main()
{
int a , b;
f >> n >> x >> D;
for(int i = 1 ; i <= n ; ++ i)
f >> A [i] . t >> A [i] . l;
g << solve ();
return 0;
}