Submission #1184091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184091		OI_Account	Cake 3 (JOI19_cake3)	C++20	100 / 100	3349 ms	19936 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 200'000;
const ll INF = 1'000'000'000'000'000;
const int S = 2 * N;

int n, k;
ll v[N + 10], c[N + 10], segVal[N + 10];
int id[N + 10], cnt[4 * N + 10];
ll seg[4 * N + 10], ans[N + 10];
pair<ll, ll> p[N + 10];

int opl[S + 10], opr[S + 10];
int ql[S + 10], qr[S + 10], q;
int lft, rght;

void readInput() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> p[i].second >> p[i].first;
}

void calcVC() {
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; i++) {
        v[i] = p[i].second;
        c[i] = p[i].first;
    }
}

void calcId() {
    for (int i = 1; i <= n; i++)
        p[i] = {v[i], i};
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; i++) {
        segVal[i] = p[i].first;
        id[p[i].second] = i;
    }
}

ll get(int k, int id = 1, int l = 1, int r = n + 1) {
    if (l + 1 == r)
        return seg[id];
    int mid = (l + r) >> 1;
    if (cnt[id << 1 | 1] < k)
        return seg[id << 1 | 1] + get(k - cnt[id << 1 | 1], id << 1, l, mid);
    return get(k, id << 1 | 1, mid, r);
}

void update(int idx, int id = 1, int l = 1, int r = n + 1) {
    if (idx < l || r <= idx)
        return;
    if (l + 1 == r) {
        cnt[id] = 1 ^ cnt[id];
        seg[id] = segVal[l] * cnt[id];
        return;
    }
    int mid = (l + r) >> 1;
    update(idx, id << 1, l, mid);
    update(idx, id << 1 | 1, mid, r);
    seg[id] = seg[id << 1] + seg[id << 1 | 1];
    cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
}

ll getAns(int l, int r) {
    while (l < lft) 
        update(id[lft--]);
    while (rght < r)
        update(id[rght++]);
    while (lft < l)
        update(id[++lft]);
    while (r < rght)
        update(id[--rght]);
    if (rght - lft + 1 < k)
        return -INF;
    return get(k - 2) + v[lft] + v[rght] - 2ll * (c[rght] - c[lft]);
}

void addQu(int a, int b, int c, int d) {
    q++;
    opl[q] = a; opr[q] = b;
    ql[q] = c; qr[q] = d;
}

void solve(int optL, int optR, int l, int r) {
    int mid = (l + r) >> 1;
    ans[mid] = getAns(optL, mid);
    int opt = optL;
    for (int i = optL + 1; i <= optR && i < mid; i++) {
        ll tmp = getAns(i, mid);
        if (tmp > ans[mid]) {
            ans[mid] = tmp;
            opt = i;
        }
    }
    if (l < mid)
        addQu(optL, opt, l, mid - 1);
    if (mid < r)
        addQu(opt, optR, mid + 1, r);
}

void calcAns() {
    addQu(1, n, 1, n);
    for (int i = 1; i <= q; i++)
        solve(opl[i], opr[i], ql[i], qr[i]);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcVC();
    calcId();
    calcAns();
    cout << *max_element(ans + 1, ans + n + 1);
    return 0;
}

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