제출 #1089322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089322		Sharky	Cake 3 (JOI19_cake3)	C++17	100 / 100	608 ms	129224 KiB

cake3

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

#define int long long

const int N = 200005;
const int M = 6e6 + 5;
const int INF = 1e18;

int n, m, ans = -INF, node = 1, sz;
pair<int, int> p[N];
int rt[M], ls[M], rs[M], cnt[M], sum[M];
vector<int> disc;

int update(int root, int ori, int pos, int l, int r) {
    ++node;
    int x = node;
    ls[x] = ls[root], rs[x] = rs[root], cnt[x] = cnt[root] + 1, sum[x] = sum[root] + ori;
    // cout << "update: " << ori << " " << l << " " << r << " node: " << x << '\n';
    if (l == r) return x;
    int mid = (l + r) / 2;
    if (pos <= mid) ls[x] = update(ls[x], ori, pos, l, mid);
    else rs[x] = update(rs[x], ori, pos, mid + 1, r);
    return x;
}

int query(int ql, int qr, int k, int l, int r) {
    // cout << "enter: " << ql << " " << qr << " " << k << " " << l << " " << r << '\n';
    if (!k) return 0;
    if (l == r) return disc[l - 1] * k;
    int mid = (l + r) / 2;
    int lc = cnt[rs[qr]] - cnt[rs[ql]];
    // cout << "lc: " << lc << '\n';
    if (lc > k) return query(rs[ql], rs[qr], k, mid + 1, r);
    return sum[rs[qr]] - sum[rs[ql]] + query(ls[ql], ls[qr], k - lc, l, mid);
}

int qry(int l, int r) {
    // cout << l << " " << r - 1 << " " << m - 2 << " " << 1 << " " << sz << '\n';
    int res = query(rt[l], rt[r - 1], m - 2, 1, sz);
    // cout << "res: " << res << '\n';
    return (p[l].second - p[r].second) * 2 + p[l].first + p[r].first + res;
}

void dnc(int l, int r, int optl, int optr) {
    // cout << "dnc: " << l << " " << r <<'\n';
    if (l > r) return;
    int mid = (l + r) / 2;
    int opt = optr, mx = -INF;
    for (int i = max(mid + m - 1, optl); i <= optr; i++) {
        // cout << "query: " << mid << " " << i << '\n';
        int res = qry(mid, i);
        // cout << "returned " << res << '\n';
        if (opt == -1) opt = i, mx = res;
        else if (res > mx) opt = i, mx = res;
    }
    ans = max(ans, mx);
    dnc(l, mid - 1, optl, opt);
    dnc(mid + 1, r, opt, optr);
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].first >> p[i].second;
        disc.push_back(p[i].first);
    }
    sort(disc.begin(), disc.end());
    disc.erase(unique(disc.begin(), disc.end()), disc.end());
    sort(p + 1, p + n + 1, [] (auto x, auto y) { return x.second < y.second; });
    rt[0] = 1;
    sz = disc.size();
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(disc.begin(), disc.end(), p[i].first) - disc.begin() + 1;
        rt[i] = update(rt[i - 1], p[i].first, pos, 1, sz);
    }
    dnc(1, n, 1, n);
    cout << ans << '\n';
}

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