Submission #1085837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085837		juliany2	Cake 3 (JOI19_cake3)	C++17	100 / 100	1129 ms	17028 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 7;
int n, k;
array<ll, 2> a[N];
int ord[N], pos[N];
ll s[N * 4], t[N * 4];
ll ans = -1e18;
int L = 1, R = 0;

void upd(int i, int x, int v = 1, int l = 1, int r = n) {
    if (l == r)
        s[v] = x, t[v] = x * a[ord[i]][1];
    else {
        int m = (l + r) / 2;
        if (i <= m)
            upd(i, x, v * 2, l, m);
        else
            upd(i, x, v * 2 + 1, m + 1, r);

        s[v] = s[v * 2] + s[v * 2 + 1];
        t[v] = t[v * 2] + t[v * 2 + 1];

    }
}

ll query(int cnt = 0, int v = 1, int l = 1, int r = n) {
    if (l == r) {
        return t[v];
    }

    int m = (l + r) / 2;
    if (cnt + s[v * 2] < k - 2)
        return t[v * 2] + query(cnt + s[v * 2], v * 2 + 1, m + 1, r);
    else
        return query(cnt, v * 2, l, m);
}

void shift(int l, int r) {
    while (R < r) {
        R++;
        upd(pos[R], 1);
    }
    while (L > l) {
        L--;
        upd(pos[L], 1);
    }
    while (R > r) {
        upd(pos[R], 0);
        R--;
    }
    while (L < l) {
        upd(pos[L], 0);
        L++;
    }
}

void dnq(int l = 1, int r = n - k + 1, int optl = 1, int optr = n) {
    if (l > r)
        return;

    int m = (l + r) / 2;

    pair<ll, int> bst = {-1e18, -1};
    for (int i = max(optl, m + k - 1); i <= optr; i++) {
        shift(m + 1, i - 1);

        bst = max(bst, {query() + a[m][1] + a[i][1] - 2 * (a[i][0] - a[m][0]), i});
    }

    ans = max(ans, bst.first);

    int optm = bst.second;

    dnq(l, m - 1, optl, optm);
    dnq(m + 1, r, optm, optr);
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> a[i][1] >> a[i][0];

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

    iota(ord + 1, ord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [&](int x, int y) { return a[x][1] > a[y][1]; });

    for (int i = 1; i <= n; i++)
        pos[ord[i]] = i;

    dnq();

    cout << ans << '\n';

    return 0;
}

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