제출 #972996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972996		Double_Slash	Cake 3 (JOI19_cake3)	C++17	24 / 100	427 ms	262144 KiB

cake3

#include <bits/stdc++.h>
#define debug(x) [&](){ auto _x = x; cerr << __LINE__ << ": " << #x << " = " << _x << endl; }()

using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()

const int INF = 1e9;
const ll LLINF = 1e18;
int n, m, v[200001], c[200001];
ll ans;
struct Node {
    int freq = 0;
    ll sum = 0;
    Node *lc = nullptr, *rc = nullptr;

    Node *pull(Node *ln, Node *rn) {
        return new Node{ln->freq + rn->freq, ln->sum + rn->sum, ln, rn};
    }

    Node *update(int i, int l, int r) {
        if (l == r) return new Node{freq + 1, sum + l};
        int m = (l + r) >> 1;
        if (i <= m) return pull(lc->update(i, l, m), rc);
        else return pull(lc, rc->update(i, m + 1, r));
    }
} *st[200001];

ll walk(Node *ln, Node *rn, int k, int l, int r) {
    if (l == r) return (ll) k * l;
    int rfreq = rn->rc ? rn->rc->freq - (ln and ln->rc ? ln->rc->freq : 0) : 0;
    int m = (l + r) >> 1;
    if (k <= rfreq) return walk(ln ? ln->rc : nullptr, rn->rc, k, m + 1, r);
    else return walk(ln ? ln->lc : nullptr, rn->lc, k - rfreq, l, m) + (rn->rc ? rn->rc->sum - (ln and ln->rc ? ln->rc->sum : 0) : 0);
}

ll calc(int l, int r) {
    if (r - l + 1 < m) return -LLINF;
    return walk(st[l - 1], st[r], m, 1, INF) - (c[r] - c[l]) * 2;
}

void dnc(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    pair<ll, int> mx{-LLINF, 0};
    for (int k = max(optl, mid + m - 1); k <= optr; ++k) {
        mx = max(mx, {calc(mid, k), k});
    }
    ans = max(ans, mx.first);
    dnc(l, mid - 1, optl, mx.second);
    dnc(mid + 1, r, mx.second, optr);
}

int main() {
    cin >> n >> m;
    vector<pair<int, int>> raw(n);
    for (auto &[b, a]: raw) cin >> a >> b;
    sort(all(raw));
    st[0] = new Node{};
    st[0]->lc = st[0]->rc = st[0];
    for (int i = 1; i <= n; ++i) {
        tie(c[i], v[i]) = raw[i - 1];
        st[i] = st[i - 1]->update(v[i], 1, INF);
    }
    ans = -LLINF;
    dnc(1, n - m + 1, m, n);
    cout << ans << endl;
}

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