Submission #1142714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142714		VMaksimoski008	Cake 3 (JOI19_cake3)	C++20	24 / 100	4097 ms	193008 KiB

cake3

#include <bits/stdc++.h>
#define ar array

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int maxn = 2e5 + 5;

vector<int> comp;

struct node {
    int cnt = 0;
    ll sum = 0;
    node *l, *r;

    node(int c=0, ll v=0) : cnt(c), sum(v), l(nullptr), r(nullptr) {}
    node(node *l, node *r) : l(l), r(r) {
        if(l) sum += l->sum, cnt += l->cnt;
        if(r) sum += r->sum, cnt += r->cnt;
    }
};

node *build(int l, int r) {
    if(l == r) return new node(0, 0);
    int tm = (l + r) / 2;
    return new node(build(l, tm), build(tm+1, r));
}

node *update(node *u, int tl, int tr, int p) {
    if(tl == tr) return new node(u->cnt + 1, u->sum + comp[p]);
    int tm = (tl + tr) / 2;
    if(p <= tm) return new node(update(u->l, tl, tm, p), u->r);
    return new node(u->l, update(u->r, tm+1, tr, p));
}

int n, m;
vector<ar<int, 2> > a(maxn);
vector<node*> R;

ll find(node *u, node *v, int tl, int tr, int k) {
    if(tl == tr) return 1ll * k * comp[tl];
    int tm = (tl + tr) / 2;
    if(u->r->cnt - v->r->cnt >= k) return find(u->r, v->r, tm+1, tr, k);
    return u->r->sum - v->r->sum + find(u->l, v->l, tl, tm, k - (u->r->cnt - v->r->cnt));
}

ll query(int l, int r, int k) {
    return find(R[r], R[l-1], 1, n, k);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i][1] >> a[i][0];
    sort(a.begin()+1, a.begin()+n+1);

    set<int> st; st.insert(-1);
    for(int i=1; i<=n; i++) st.insert(a[i][1]);
    comp = vector<int>(st.begin(), st.end());

    R.push_back(build(1, n));
    for(int i=1; i<=n; i++) {
        int p = lower_bound(comp.begin(), comp.end(), a[i][1]) - comp.begin();
        R.push_back(update(R[i-1], 1, n, p));
    }

    ll ans = -1e18;
    for(int i=1; i<=n; i++)
        for(int j=i+m-1; j<=n; j++)
            ans = max(ans, a[i][1] + a[j][1] + 2ll * (a[i][0] - a[j][0]) + query(i+1, j-1, m-2));
    cout << ans << '\n';
}

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