Submission #1172266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172266		jill	Cake 3 (JOI19_cake3)	C++20	0 / 100	109 ms	274572 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 5e6 + 5;

struct WT {
    struct node {
        int l, r;
        vector<ll> x;
        vector<ll> s;
    } t[nmax];
    ll lo, hi;
    
    int build(vector<ll> seq, ll a, ll b) {  
        static int idx = 0;
        if(seq.empty()) return -1;
        int cur = idx++;
        if(a == b) return cur;
        int mid = (a + b) >> 1;
        t[cur].x.resize(seq.size());
        t[cur].s.resize(seq.size());
        vector<ll> left_seq, right_seq;
        for (size_t i = 0; i < seq.size(); i++) {
            if(seq[i] <= mid) {
                t[cur].x[i] = 0;
                t[cur].s[i] = 0;
                left_seq.push_back(seq[i]);
            } else {
                t[cur].x[i] = 1;
                t[cur].s[i] = seq[i];
                right_seq.push_back(seq[i]);
            }
        }
        for (size_t i = 1; i < seq.size(); i++) {
            t[cur].x[i] += t[cur].x[i-1];
            t[cur].s[i] += t[cur].s[i-1];
        }
        t[cur].l = build(left_seq, a, mid);
        t[cur].r = build(right_seq, mid+1, b);
        return cur;
    }
    
    int map_left(int node, int i) {
        return i - (i >= 0 ? t[node].x[i] : 0);
    }
    int map_right(int node, int i) {
        // Số phần tử bên phải trong [0,i] là t[node].x[i]
        return (i >= 0 ? t[node].x[i] : 0) - 1;
    }
    
    int countRight(int node, int l, int r) {
        if(l > r || l < 0) return 0;
        int res = t[node].x[r];
        if(l > 0) res -= t[node].x[l-1];
        return res;
    }
    
    ll sumRight(int node, int l, int r) {
        if(l > r || l < 0) return 0LL;
        ll res = t[node].s[r];
        if(l > 0) res -= t[node].s[l-1];
        return res;
    }
    
    ll getUtil(int node, ll a, ll b, int l, int r, int k) {
        if(l > r || k <= 0) return 0LL;
        if(a == b) { 
            int cnt = r - l + 1;
            int take = min(cnt, k);
            return (ll) take * a;
        }
        int mid = (a + b) >> 1;
        int cntR = countRight(node, l, r); 
        if(cntR >= k) {
            int newL = map_right(node, l);
            int newR = map_right(node, r);
            return getUtil(t[node].r, mid+1, b, newL, newR, k);
        } else {
            ll sumR = sumRight(node, l, r);
            int newL = map_left(node, l);
            int newR = map_left(node, r);
            return sumR + getUtil(t[node].l, a, mid, newL, newR, k - cntR);
        }
    }
    
    ll get(int l, int r, int k) {
        if(l > r) return 0LL;
        return getUtil(0, lo, hi, l, r, k);
    }
} tree;

int n, m;
ll ans;
vector<array<ll, 2>> a; 

int cost(int l, int r) {
    return tree.get(l+1, r-1, m-2) - 2 * abs(a[l][1] - a[r][1]) + a[r][0] + a[l][0];
}

void calc(int l, int r, int opl, int opr) {
    if(l > r) return;
    int mid = (l + r) >> 1;
    pair<ll, int> best = {-LLONG_MAX, max(0, mid - m + 1)};
    if(mid - m + 1 >= 0) {
        for (int k = opl; k <= min(mid - m + 1, opr); k++) {
            best = max(best, { (ll) cost(k, mid), k });
        }
        ans = max(ans, best.first);
        calc(l, mid - 1, opl, best.second);
    }
    calc(mid + 1, r, best.second, opr);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++){
        cin >> a[i][0] >> a[i][1];
    }
    sort(a.begin(), a.end(), [](auto x, auto y) {
        return x[1] < y[1];
    });
    vector<ll> b;
    for (int i = 0; i < n; i++){
        b.push_back(a[i][0]);
    }
    ll mn = *min_element(b.begin(), b.end());
    ll mx = *max_element(b.begin(), b.end());
    tree.lo = mn;
    tree.hi = mx;
    tree.build(b, mn, mx);
    calc(0, n - 1, 0, n - 1);
    cout << ans;
    return 0;
}

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