Submission #947348

#	Time	Username	Problem	Language	Result	Execution time	Memory
947348		caterpillow	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	604 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

*/

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;
    }
};

const int sz = 1 << 18;
vt<ptr> roots;

ptr pull(ptr l, ptr r) {
    ptr res = new Node(l->val + r->val, l->cnt + r->cnt);
    res->l = l;
    res->r = r;
    return res;
}

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 pull(update(n->l, val, i, l, m), n->r);
    else return pull(n->l, update(n->r, val, i, m + 1, r));
}

ll walk(ptr ln, ptr rn, int k, int l = 0, int r = sz - 1) {
    if (l == r) return k ? rn->val - ln->val : 0ll;
    int m = (l + r) / 2;
    int rhs = rn->r->cnt - ln->r->cnt;
    if (rhs >= k) return walk(ln->r, rn->r, k, m + 1, r); // go right
    else return walk(ln->l, rn->l, k - rhs, l, m) + rn->r->val - ln->r->val;
}

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 0ll;
    int m = (l + r) / 2;
    pl best = {0, -1};
    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;

    roots.resize(n + 1);
    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:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main() {
      | ^~~~

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