Submission #1219045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219045		395333em	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	328 KiB

cake3

#include <bits/stdc++.h>
#define int long long
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define emb emplace_back

using namespace std;

const int inf = 1e18;
const int N = 2e5 + 5;

int n, m, ans = -inf, id;
tiii a[N];
unordered_map <int, int> com, moc;

struct persistent {
    struct node {
        int sum, cnt;
        node *l, *r;
        node() : sum(0), cnt(0), l(0), r(0) {}
    };
    typedef node* pnode;
    pnode root[N];
    void build(int l, int r, pnode &i){
        i = new node();
        if (l == r) return;
        int mid = (l + r) / 2;
        build(l, mid, i->l), build(mid + 1, r, i->r);
    }
    void update(int l, int r, pnode &i, pnode j, int idx, int val){
        i = new node(*j);
        i->sum += val;
        i->cnt += 1;
        if (l == r) return i->sum = val, i->cnt = 1, void();
        int mid = (l + r) / 2;
        if (idx <= mid) update(l, mid, i->l, j->l, idx, val);
        else update(mid + 1, r, i->r, j->r, idx, val);
    }
    int query(int l, int r, pnode i, pnode j, int k){
        if (l == r) return i->sum - j->sum;
        int mid = (l + r) / 2;
        if (i->r->cnt - j->r->cnt >= k) return query(mid + 1, r, i->r, j->r, k);
        else return i->r->sum - j->r->sum + query(l, mid, i->l, j->l, k - i->r->cnt);
    }
    int cal(int l, int r){
        return query(1, n, root[r], root[l - 1], m) - 2 * (get <0> (a[r]) - get <0> (a[l]));
    }
} seg;

void dac(int l, int r, int left, int right){
    if (r < l) return;
    int mid = (l + r) / 2;
    int mx = -inf, idx = left;
    for (int i = left; i <= min(right, mid - m + 1); i++) {
        int c = seg.cal(i, mid);
        if (c > mx) {
            mx = c;
            idx = i;
        }
    }
    dac(l, mid - 1, left, idx);
    dac(mid + 1, r, idx, right);
    ans = max(ans, mx);
}

int32_t main(){
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    vector <pii> temp;
    for (int i = 1; i <= n; i++) {
        auto &[c, v, idx] = a[i];
        cin >> v >> c;
        idx = i;
        temp.emb(v, idx);
    }
    sort(temp.begin(), temp.end());
    sort(a + 1, a + 1 + n);
    for (auto [v, idx] : temp) {
        com[idx] = ++id;
    }
    seg.build(1, n, seg.root[0]);
    for (int i = 1; i <= n; i++) {
        auto [c, v, idx] = a[i];
        seg.update(1, n, seg.root[i], seg.root[i - 1], com[idx], v);
    }
    dac(m, n, 1, n);
    cout << ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76