Cod sursa(job #2709140)

Utilizator DordeDorde Matei Dorde Data 19 februarie 2021 19:44:12
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 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);
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;
}