Pagini recente » Cod sursa (job #2166198) | Cod sursa (job #3153365) | Cod sursa (job #3272604) | Cod sursa (job #2901622) | Cod sursa (job #2708797)
#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);
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 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);
}
} H;
int main()
{
int n , x , D;
f >> n >> x >> D;
for(int i = 1 ; i <= n ; ++ i){
int a , b;
f >> a >> b;
A [i] = {1 + (x - a) / D , b};
}
sort (A + 1 , A + 1 + n);
int last = A [1] . t;
H . push (A [1] . l);
ll r = 0;
for(int i = 2 ; i <= n ; ){
while (i <= n && A [i] . t == last)
H . push (A [i] . l) , ++ i;
r += H . top ();
H . pop ();
last = A [i] . t;
}
g << r;
return 0;
}