Subtask 1-2:

Để qua ~40%~ test đầu các bạn có thể xét từng ~k~ rồi xử lí độc lập như sau:

Sắp xếp ~k~ công việc đầu theo ~d_i~. Gọi ~S~ là tập heap_max lưu trữ các công việc chưa được làm Xét từng thời điểm ~d~ theo thứ tự giảm dần, đến ~d~ của việc nào thì ném việc đó vào tập ~S~. Sau khi ném xong thì chọn việc sẽ làm tại thời điểm ~d~ là một việc nào đó trong tập ~S~ (hiển nhiên là việc có p lớn nhất).

Subtask 3:

Ta sẽ tìm cách xây dựng mối liên kết giữa công việc ~k~ vào bài toán ~(k-1)~ công việc đã xét ở trước. Vậy, công việc ~k~ có 2 trường hợp thay đổi kết quả bài toán là :

~1)~ Công việc ~k~ có thêm vào tập các công việc được làm

~2)~ Công việc ~k~ thay thế một việc trong tập các công việc được làm

Để kiểm tra ~1)~ ta có điều kiện cần và đủ là (số lượng công việc có deadline bé hơn hoặc bằng ~i~) ~\leq i~ ~\{\forall~ ~i \in [1, \inf)\}~. Ta có thể xây dựng cây Segment Tree Max (Lazy Segment Tree), quản lí thời điểm và đặt trước cho phần tử thứ ~i~ là ~-i~. Từ đó, công việc ~k~ có thể thêm vào nếu phần tử lớn nhất trên cây SegTree bé hơn ~0~.

Còn nếu không đặt được thêm công việc ~k~ thì nó sẽ cố thay thế ~1~ việc nào đó trong tập được làm. Cách xử lí là ta sẽ thêm công việc ~k~ vào, lúc này trên cây SegTree sẽ có một số vị trí bằng ~1~ thì ta sẽ phải bắt buộc bỏ đi ~1~ công việc có p nhỏ nhất trong đoạn từ ~1~ đến vị trí đầu tiên mà bằng ~1~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define ls(x) (x*2)
#define rs(x) (x*2+1)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int maxn = 100000;
const int maxh = 10;
const int oo = 4e18;
int n;
int d[maxn+1], p[maxn+1];

int maxi[maxn*maxh], vtmax[maxn*maxh], l[maxn*maxh], r[maxn*maxh];
bool lazy[maxn*maxh];
int lazyAdd[maxn*maxh];
multiset<pii> jobs[maxn*maxh];

pii better(pii x, pii y) {
    if (x.first >= y.first) return x;
    return y;
}

pii merger(int x,int y) {
    return better({maxi[x], vtmax[x]}, {maxi[y], vtmax[y]});
}

void initIT(int i,int x,int y) {
    l[i] = x, r[i] = y, lazy[i] = false, lazyAdd[i] = 0;
    jobs[i].clear();
    if (x==y) {
        maxi[i] = -x;
        vtmax[i] = x;
    } else {
        int m = (x+y)/2;
        initIT(ls(i),x,m);
        initIT(rs(i),m+1,y);
        pii tmp = merger(ls(i), rs(i));
        maxi[i] = tmp.first;
        vtmax[i] = tmp.second;
    }
}

void pushIT(int i) {
    if (lazy[i]) {
        lazy[i] = false;
        maxi[i] += lazyAdd[i];
        if (l[i]!=r[i]) {
            lazy[ls(i)] = true;
            lazy[rs(i)] = true;
            lazyAdd[ls(i)] += lazyAdd[i];
            lazyAdd[rs(i)] += lazyAdd[i];
        }
        lazyAdd[i] = 0;
    }
}


void addValueIT(int i,int x,int y,int v) {
    pushIT(i);
    if (y<l[i] || x>r[i]) return;
    if (x<=l[i] && r[i]<=y) {
        lazy[i] = true;
        lazyAdd[i]+=v;
        pushIT(i);
        return;
    }
    addValueIT(ls(i),x,y,v);
    addValueIT(rs(i),x,y,v);
    pii tmp = merger(ls(i),rs(i));
    maxi[i] = tmp.first;
    vtmax[i] = tmp.second;
}


pii getMaxIT(int i,int x,int y) {
    pushIT(i);
    if (y<l[i] || x>r[i]) return {-oo, -oo};
    if (x<=l[i] && r[i]<=y) return {maxi[i], vtmax[i]};
    pii left = getMaxIT(ls(i),x,y);
    pii right = getMaxIT(rs(i),x,y);
    return better(left, right);
}

void addJobs(int i,int d,int p) {
    if (d<l[i] || d>r[i]) return;
    jobs[i].insert({p,d});
    if (l[i]!=r[i]) {
        addJobs(ls(i),d,p);
        addJobs(rs(i),d,p);
    }
}

void removeJobs(int i,int d,int p) {
    if (d<l[i] || d>r[i]) return;
    jobs[i].erase(jobs[i].find({p,d}));
    if (l[i]!=r[i]) {
        removeJobs(ls(i),d,p);
        removeJobs(rs(i),d,p);
    }
}

pii findWorstJob(int i,int x,int y) {
    if (y<l[i] || x>r[i]) return {oo, oo};
    if (x<=l[i] && r[i]<=y) {
        if (sz(jobs[i])==0) return {oo, oo};
        return (*jobs[i].begin());
    }
    pii left = findWorstJob(ls(i),x,y);
    pii right = findWorstJob(rs(i),x,y);
    return min(left, right);
}



main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n;
    rep(i,1,n+1) cin >> d[i] >> p[i];
    initIT(1,1,maxn);

    int res = 0;
    rep(i,1,n+1) {
        addValueIT(1, d[i], maxn, 1);
        addJobs(1, d[i], p[i]);
        res += p[i];
        pii tmp = getMaxIT(1, 1, maxn);
        if (tmp.first > 0) {
            pii worstjob = findWorstJob(1, 1, tmp.second);
            removeJobs(1, worstjob.second, worstjob.first);
            addValueIT(1, worstjob.second, maxn, -1);
            res-=worstjob.first;
        }
        cout << res << '\n';
    }
}