Cod sursa(job #2708797)

Utilizator DordeDorde Matei Dorde Data 19 februarie 2021 13:59:40
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#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;
}