Submission #953974

#	Time	Username	Problem	Language	Result	Execution time	Memory
953974		Pring	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	2396 KiB

cake3

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 200005, LG = 35, MXC = 1000000005;
int n, m;
pii p[MXN];
int ans;

namespace PSMG {
#define mid ((l + r) >> 1)
    int val[MXN * LG], cnt[MXN * LG], L[MXN * LG], R[MXN * LG], nc;
    vector<int> rt;

    int new_node(int ref) {
        val[nc] = val[ref];
        cnt[nc] = cnt[ref];
        L[nc] = L[ref];
        R[nc] = R[ref];
        return nc++;
    }

    int modify(int id, int l, int r, int p, int v) {
        id = new_node(id);
        if (l + 1 == r) {
            val[id] += p * v;
            cnt[id] += v;
            return id;
        }
        if (p < mid) L[id] = modify(L[id], l, mid, p, v);
        else R[id] = modify(R[id], mid, r, p, v);
        val[id] = val[L[id]] + val[R[id]];
        cnt[id] = cnt[L[id]] + cnt[R[id]];
        return id;
    }

    void init() {
        nc = 2;
        rt.push_back(1);
        FOR(i, 0, n) {
            rt.push_back(modify(rt.back(), 0, MXC, p[i].sc, 1));
        }
    }

    int query(int idl, int idr, int l, int r, int bnd) {
        // debug(l, r, bnd, cnt[idl], cnt[idr]);
        if (bnd == cnt[idr] - cnt[idl]) {
            // debug(val[idl], val[idr]);
            return val[idr] - val[idl];
        }
        int rcnt = cnt[R[idr]] - cnt[R[idl]];
        if (rcnt >= bnd) return query(R[idl], R[idr], mid, r, bnd);
        return val[R[idr]] - val[R[idl]] + query(L[idl], L[idr], l, mid, bnd - rcnt);
    }

    int calc(int l, int r) {
        // debug(l, r);
        return query(rt[l], rt[r], 0, MXC, m - 2);
    }
#undef mid
}

pii calc(int id, int l, int r) {
    pii ans = mp(0LL, -1LL);
    FOR(i, l, r + 1) {
        if (id - i + 1 < m) continue;
        ans = max(ans, mp(PSMG::calc(i + 1, id) + p[id].sc - 2 * p[id].fs + p[i].sc + 2 * p[i].fs, i));
        // debug(i + 1, id, ans.fs);
    }
    return ans;
}

void solve(int l, int r, int kl, int kr) {
    if (l == r) return;
    // debug(l, r, kl, kr);
    int mid = (l + r) >> 1;
    auto [val, k] = calc(mid, kl, kr);
    // debug(mid, val, k);
    ans = max(ans, val);
    solve(l, mid, kl, k);
    solve(mid + 1, r, k, kr);
}

void miku() {
    cin >> n >> m;
    FOR(i, 0, n) cin >> p[i].sc >> p[i].fs;
    sort(p, p + n);
    PSMG::init();
    solve(0, n, 0, n);
    cout << ans << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

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