Submission #153380

#	Time	Username	Problem	Language	Result	Execution time	Memory
153380		fedoseevtimofey	Cake 3 (JOI19_cake3)	C++14	100 / 100	1267 ms	107664 KiB

cake3

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;

const int N = 2e5 + 7;

const ll Inf = 5e18;

struct Node {
    ll sum;
    int cnt, L, R; 
    Node(int val) {
        sum = val;
        cnt = 1;
        L = R = -1;
    }
    Node(ll sum, int cnt) : sum(sum), cnt(cnt), L(-1), R(-1) {}
    Node(ll sum, int cnt, int L, int R) : sum(sum), cnt(cnt), L(L), R(R) {}
    Node() : sum(0), cnt(0), L(-1), R(-1) {}
};

vector <Node> t;

int build(int l, int r) {
    if (l == r) {
        t.push_back(Node());
        return (int)t.size() - 1;
    } else {
        int m = (l + r) >> 1;
        int L = build(l, m);
        int R = build(m + 1, r);
        t.push_back(Node(0, 0, L, R));
        return (int)t.size() - 1;
    }
}

ll val[N];

int modify(int id, int v, int l, int r) {
    if (l == r) {
        t.push_back(Node(t[v].sum + val[id], t[v].cnt + 1));
        return (int)t.size() - 1;
    } else {
        int m = (l + r) >> 1;
        if (id <= m) {
            int L = modify(id, t[v].L, l, m);
            int R = t[v].R;
            t.push_back(Node(t[L].sum + t[R].sum, t[L].cnt + t[R].cnt, L, R));
            return (int)t.size() - 1;
        } else {
            int L = t[v].L;
            int R = modify(id, t[v].R, m + 1, r);
            t.push_back(Node(t[L].sum + t[R].sum, t[L].cnt + t[R].cnt, L, R));
            return (int)t.size() - 1;
        }
    }
}
ll get(int k, int vl, int vr, int l, int r) {
    if (l == r) {
        return (ll)k * val[l];
    } else {
        int m = (l + r) >> 1;
        if (t[t[vr].R].cnt - t[t[vl].R].cnt >= k) {
            return get(k, t[vl].R, t[vr].R, m + 1, r);
        } else {
            return t[t[vr].R].sum - t[t[vl].R].sum + get(k - (t[t[vr].R].cnt - t[t[vl].R].cnt), t[vl].L, t[vr].L, l, m);
        }
    }
}

vector <int> roots;
int sz, n, m;

ll ans = -5e18;
vector <pair <int, int>> a;

ll get(int l, int r) {
    return get(m, roots[l], roots[r + 1], 0, sz - 1) - 2 * a[r].first + 2 * a[l].first;
}

void rec(int l, int r, int opt_l, int opt_r) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    int opt_m = opt_r;
    ll res = -5e18;
    for (int i = max(mid + m - 1, opt_l); i <= opt_r; ++i) {
        ll cur = get(mid, i);
        ans = max(ans, cur);
        if (cur > res) {
            res = cur;
            opt_m = i;
        }
    }
    rec(l, mid - 1, opt_l, opt_m);
    rec(mid + 1, r, opt_m, opt_r);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif    
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i].second >> a[i].first;
    sort(a.begin(), a.end());
    vector <int> cm;
    for (int i = 0; i < n; ++i) cm.push_back(a[i].second);
    sort(cm.begin(), cm.end());
    cm.resize(unique(cm.begin(), cm.end()) - cm.begin());
    sz = cm.size();
    roots.push_back(build(0, sz - 1));
    for (int i = 0; i < (int)cm.size(); ++i) val[i] = cm[i];
    for (int i = 0; i < n; ++i) {
        int id = lower_bound(cm.begin(), cm.end(), a[i].second) - cm.begin();
        roots.push_back(modify(id, roots.back(), 0, sz - 1));
    }
    rec(0, n - 1, 0, n - 1);
    cout << ans << '\n';
}

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