Submission #972989

#	Time	Username	Problem	Language	Result	Execution time	Memory
972989		Double_Slash	Cake 3 (JOI19_cake3)	C++17	24 / 100	393 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;
typedef pair<int, int> pint;
#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 l, r, freq = 0;
    ll sum = 0;
    Node *lc = nullptr, *rc = nullptr;

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

ll walk(Node *l, Node *r, int k) {
    if (r->l == r->r) return (ll) k * r->l;
    int rfreq = r->rc ? r->rc->freq - (l and l->rc ? l->rc->freq : 0) : 0;
    if (k <= rfreq) return walk(l ? l->rc : nullptr, r->rc, k);
    else return walk(l ? l->lc : nullptr, r->lc, k - rfreq) + (r->rc ? r->rc->sum - (l and l->rc ? l->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) - (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{1, INF};
    for (int i = 1; i <= n; ++i) {
        tie(c[i], v[i]) = raw[i - 1];
        st[i] = st[i - 1]->update(v[i]);
    }
    ans = -LLINF;
    dnc(1, n - m + 1, m, n);
    cout << ans << endl;
}

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