Submission #947352

#	Time	Username	Problem	Language	Result	Execution time	Memory
947352		caterpillow	Cake 3 (JOI19_cake3)	C++17	100 / 100	856 ms	191364 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll,ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define F0R(i, b) FOR(i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;

/*

as l increases, the optimal r also increases

*/
const int sz = 1 << 18;

using ptr = struct Node*;

struct Node {
    ll val;
    int cnt;
    ptr l, r;
    Node(ll _val, int _cnt) {
        val = _val;
        cnt = _cnt;
        l = r = 0;
    }

    Node(ptr _l, ptr _r) {
        l = _l;
        r = _r;
        val = cnt = 0;
        if (l) val += l->val, cnt += l->cnt;
        if (r) val += r->val, cnt += r->cnt;
    }
};

ptr update(ptr n, ll val, int i, int l = 0, int r = sz - 1) {
    if (l == r) return new Node(val, 1);
    int m = (l + r) / 2;
    if (i <= m) return new Node(update(n->l, val, i, l, m), n->r); 
    else return new Node(n->l, update(n->r, val, i, m + 1, r));
}

ll walk(ptr l, ptr r, int k, int lo = 0, int hi = sz - 1) { // sum of k largest
    if (lo == hi) return r->val - l->val;
    int m = (lo + hi) / 2;
    int rhs = r->r->cnt - l->r->cnt;
    if (rhs >= k) return walk(l->r, r->r, k, m + 1, hi);
    else return walk(l->l, r->l, k - rhs, lo, m) + r->r->val - l->r->val;
}

ptr roots[sz];

int n, k;
vt<pl> cakes;

ll query(int l, int r) {
    if (l > r) return 0ll;
    return walk(roots[l], roots[r + 1], k - 2);
}

ll dnc(int l, int r, int lo, int hi) {
    if (l > r) return -INF;
    int m = (l + r) / 2;
    pl best = {-INF, hi};
    FOR (i, lo, hi + 1) {
        if (i - m + 1 < k) continue;
        ll val = query(m + 1, i - 1) - (cakes[i].f - cakes[m].f) + cakes[i].s + cakes[m].s;
        best = max(best, pl{val, i});
    }
    return max({best.f, dnc(l, m - 1, lo, best.s), dnc(m + 1, r, best.s, hi)});
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> k;
    cakes.resize(n); // colour, value
    F0R (i, n) cin >> cakes[i].s >> cakes[i].f, cakes[i].f *= 2;
    sort(all(cakes));

    vt<pl> sorted(n);
    F0R (i, n) sorted[i] = {cakes[i].s, i};
    sort(all(sorted));
    vt<int> rind(n);
    F0R (i, n) rind[sorted[i].s] = i;

    ptr root = new Node(0, 0);
    roots[0] = root->l = root->r = root;
    F0R (i, n) {
        roots[i + 1] = update(roots[i], cakes[i].s, rind[i]);
    }

    cout << dnc(0, n - 1, 0, n - 1) << endl;

}

Compilation message (stderr)

cake3.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main() {
      | ^~~~

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