题解 | #购物#

/*
*  不是特别懂,这个思路,照着题解敲一遍,日后再来,好好研究!!! 
*/


#include <bits/stdc++.h>


using namespace std;

typedef long long ll;

const ll maxn = 1000000;

vector<ll> seg(maxn), seg2(maxn); // 两个线段树! 


void pushup(int node) {
    if (seg[node << 1] <= seg[node << 1 | 1]) {
        seg[node] = seg[node << 1];
        seg2[node] = seg2[node << 1];
    } else {
        seg[node] = seg[node << 1 | 1];
        seg2[node] = seg2[node << 1 | 1];
    }
}

void build(int l, int r, int node) {
    if (l == r) {
        seg[node] = 0;
        seg2[node] = l;
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, node << 1); // 左孩子
    build(mid + 1, r, node << 1 | 1); // 右孩子!
    pushup(node);
}

pair<ll, ll> nums[maxn];

ll ret(0);

void update(int l, int r, int pos, int node, ll ai, ll c) {
    if (l == r) {
        seg[node] = max(seg[node], ai) + c;
        ret = max(ret, seg[node]);
        return ;
    }

    int mid = (l + r) >> 1;
    if (pos <= mid) {
        update(l, mid, pos, node << 1, ai, c);
    } else {
        update(mid + 1, r, pos, node << 1 | 1, ai, c);
    }
    pushup(node);

}


int main() {
    int n, m;
    cin >> n >> m;
    build(1, m, 1);
    vector<ll> a(n + 1), s(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> s[i];
        nums[i] = make_pair(a[i], s[i]);
    }

    sort(nums + 1, nums + n + 1);

    for (int i = 1; i <= n; i++) {
        int pos = seg2[1];
        update(1, m, pos, 1, nums[i].first, nums[i].second);
    }
    cout << ret << endl;
    return 0;
}