Submission #1127570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127570		Zero_OP	Cake 3 (JOI19_cake3)	C++17	100 / 100	979 ms	13760 KiB

cake3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

const int MAX = 2e5 + 5;
const ll inf = 2e18;

int N, K, M;
ll ans;
vector<int> v;
struct cake{
    ll V, C;
    cake() : V(0), C(0) {}
    cake(int V, int C) : V(V), C(C) {}
    bool operator < (const cake& o){
        return make_pair(C, -V) < make_pair(o.C, -o.V);
    }

    friend istream& operator >> (istream& in, cake& c){
        return in >> c.V >> c.C;
    }
} cakes[MAX];

struct segment_tree{
    vector<ll> st;
    vector<int> cnt;
    segment_tree(int n) : st(n << 2), cnt(n << 2) {}

    void update(int id, int l, int r, int pos, int delta){
        if(l == r){
            cnt[id] += delta;
            st[id] += delta * v[l];
        } else{
            int mid = l + r >> 1;
            if(pos <= mid) update(id << 1, l, mid, pos, delta);
            else update(id << 1 | 1, mid + 1, r, pos, delta);
            st[id] = st[id << 1] + st[id << 1 | 1];
            cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
        }
    }

    ll walk(int id, int l, int r, int kth){
        if(cnt[id] < kth) return -inf;
        if(l == r){
            assert(cnt[id] >= kth);
            return 1LL * kth * v[l];
        } else{
            int mid = l + r >> 1;
            if(cnt[id << 1 | 1] < kth) return st[id << 1 | 1] + walk(id << 1, l, mid, kth - cnt[id << 1 | 1]);
            else return walk(id << 1 | 1, mid + 1, r, kth);
        }
    }
};

segment_tree tr(0);

int lt, rt;

void shift(int l, int r){
    while(rt < r) tr.update(1, 0, M - 1, cakes[++rt].V, +1);
    while(l < lt) tr.update(1, 0, M - 1, cakes[--lt].V, +1);
    while(r < rt) tr.update(1, 0, M - 1, cakes[rt--].V, -1);
    while(lt < l) tr.update(1, 0, M - 1, cakes[lt++].V, -1);
}

ll cost(int l, int r){
    shift(l, r);
    return tr.walk(1, 0, M - 1, K) - 2 * (cakes[r].C - cakes[l].C);
}

void solve(int l, int r, int optl, int optr){
    if(l > r) return;
    int m = l + r >> 1, optm = optl;
    ll result = -inf;
    for(int i = max(m + K - 1, optl); i <= optr; ++i){
        if(maximize(result, cost(m, i))){
            optm = i;
        }
    }

//    cout << m << " : " << optm << '\n';

    ans = max(ans, result);
    if(m < r) solve(m + 1, r, optm, optr);
    if(l < m) solve(l, m - 1, optl, optm);
}

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N >> K;
    for(int i = 1; i <= N; ++i){
        cin >> cakes[i];
    }

    sort(cakes + 1, cakes + 1 + N);

    for(int i = 1; i <= N; ++i) v.push_back(cakes[i].V);

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 1; i <= N; ++i) cakes[i].V = lower_bound(v.begin(), v.end(), cakes[i].V) - v.begin();

    M = (int)v.size();
    tr = segment_tree(M);
    ans = -inf;
    lt = 1, rt = 0;

    solve(1, N - K + 1, K, N);
    cout << ans << '\n';

    return 0;
}

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