Submission #1141168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141168		anmattroi	Cake 3 (JOI19_cake3)	C++17	100 / 100	466 ms	81400 KiB

cake3

/*******************************************

Task: JOI19_Cake3
Link: https://oj.uz/problem/view/JOI19_cake3

*******************************************/

#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
using li = pair<int64_t, int>;

int n, k;
ii a[maxn];

template<class T> inline constexpr void cmax(T &x, const T &y) {if (x < y) x = y;}

int64_t sum[22*maxn];
int b[maxn], n1 = 0, root[maxn];
int it[22*maxn], L[22*maxn], R[22*maxn], nt = 0;

int build(int lo = 1, int hi = n1) {
    if (lo == hi) return ++nt;
    int cur = ++nt, mid = (lo + hi) >> 1;
    L[cur] = build(lo, mid);
    R[cur] = build(mid+1, hi);
    return cur;
}

int upd(int u, int oldver, int lo = 1, int hi = n1) {
    if (lo == hi) {
        ++nt;
        it[nt] = it[oldver] + 1;
        sum[nt] = sum[oldver] + b[lo];
        return nt;
    }
    int cur = ++nt, mid = (lo + hi) >> 1;
    if (u <= mid) {
        L[cur] = upd(u, L[oldver], lo, mid);
        R[cur] = R[oldver];
    } else {
        L[cur] = L[oldver];
        R[cur] = upd(u, R[oldver], mid+1, hi);
    }
    it[cur] = it[L[cur]] + it[R[cur]];
    sum[cur] = sum[L[cur]] + sum[R[cur]];
    return cur;
}

int64_t kth(int k, int v1, int v2, int lo = 1, int hi = n1) {
    if (lo == hi)
        return 1LL * k * b[lo];
    int mid = (lo + hi) >> 1, phai = it[R[v2]]-it[R[v1]];
    if (k > phai) return kth(k-phai, L[v1], L[v2], lo, mid) + sum[R[v2]] - sum[R[v1]];
    return kth(k, R[v1], R[v2], mid+1, hi);
}

int64_t kq[maxn];

void solve(int l = 1, int r = n, int optl = 1, int optr = n) {
    int m = (l + r) / 2;
    li Best = {LLONG_MIN, optr};
    for (int i = max(m+k-1, optl); i <= optr; i++) cmax(Best, li{kth(k, root[m-1], root[i]) - 2LL * (a[i].se-a[m].se), i});
    kq[m] = Best.fi; int opt = Best.se;
    if (l < m) solve(l, m-1, optl, opt);
    if (r > m) solve(m+1, r, opt, optr);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1, [&](ii x, ii y) {return x.se < y.se;});

    for (int i = 1; i <= n; i++) b[++n1] = a[i].fi;
    sort(b + 1, b + n1 + 1);
    n1 = unique(b + 1, b + n1 + 1) - b - 1;

    root[0] = build();
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(b + 1, b + n1 + 1, a[i].fi) - b;
        root[i] = upd(p, root[i-1]);
    }
    for (int i = 1; i <= n; i++) kq[i] = LLONG_MIN;
    solve();
    cout << *max_element(kq + 1, kq + n + 1);

}

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