제출 #1160471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160471		Perl32	Cake 3 (JOI19_cake3)	C++20	100 / 100	466 ms	116756 KiB

cake3

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template<typename T> bool ckmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
constexpr ll infl = 0x3f3f3f3f3f3f3f3f;

struct WT {
    vector<vector<int>> t, pref;
    vector<vector<ll>> sm;
    vector<int> srt;
    int sz;

    WT(vector<int>& a) {
        srt = a;
        ranges::sort(srt);
        srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
        sz = 1;
        while (sz < (int) srt.size()) sz <<= 1;
        t.resize(sz << 1);
        sm.resize(sz << 1);
        pref.resize(sz << 1);
        t[1] = a;
        for (auto& x : t[1]) x = lower_bound(srt.begin(), srt.end(), x) - srt.begin();
        build(1, 0, srt.size());;
    }

    void build(int x, int lx, int rx) {
        if (lx + 1 == rx) return;
        int m = (lx + rx) >> 1;
        sm[x].resize(t[x].size() + 1);
        pref[x].resize(t[x].size() + 1);
        sm[x][0] = pref[x][0] = 0;
        for (int i = 0; i < (int) t[x].size(); ++i) {
            int v = t[x][i], le = t[x][i] < m;
            pref[x][i + 1] = pref[x][i] + le;
            sm[x][i + 1] = sm[x][i] + le * srt[v];
            if (le) {
                t[x << 1].push_back(v);
            } else {
                t[x << 1 | 1].push_back(v);
            }
        }
        build(x << 1, lx, m);
        build(x << 1 | 1, m, rx);
    }

    ll get(int l, int r, int k, int x, int lx, int rx) {
        if (lx + 1 == rx) return 1ll * k * srt[lx];
        int m = (lx + rx) >> 1, lb = pref[x][l], rb = pref[x][r], lft = rb - lb;
        if (lft >= k) return get(lb, rb, k, x << 1, lx, m);
        return sm[x][r] - sm[x][l] + get(l - lb, r - rb, k - lft, x << 1 | 1, m, rx);
    }

    ll get(int l, int r, int k) {
        return get(l, r, k, 1, 0, srt.size());
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<array<int, 2>> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i][1] >> a[i][0];
    sort(a.begin(), a.end());
    vector<int> val(N);
    for (int i = 0; i < N; ++i) {
        val[i] = -a[i][1];
    }
    WT tt(val);
    auto cost = [&](int l, int r) { // [l, r]
        return 2 * a[l][0] - 2 * a[r][0] + a[l][1] + a[r][1] - tt.get(l + 1, r, K - 2);
    };
    ll ans = -infl;
    auto divi = [&](auto&& self, int lx, int rx, int optl, int optr) {
        if (lx > rx) return;
        int m = (lx + rx) >> 1, opt = max(0, m - K + 1);
        if (m - K + 1 > -1) {
            ll nw = cost(opt, m);
            for (int i = optl; i <= min(m - K + 1, optr); ++i) {
                if (ckmax(nw, cost(i, m))) opt = i;
            }
            ans = max(ans, nw);
            self(self, lx, m - 1, optl, opt);
        }
        self(self, m + 1, rx, opt, optr);
    };
    divi(divi, 0, N - 1, 0, N - 1);
    cout << ans;
}

/*

 */

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