Submission #931968

#	Time	Username	Problem	Language	Result	Execution time	Memory
931968		velislavgarkov	Cake 3 (JOI19_cake3)	C++14	100 / 100	426 ms	17468 KiB

cake3

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=2e5+10;
const long long INF=1e15;
struct Cake {
    long long v;
    long long c;
    int ind;
};
bool cmpc(Cake a, Cake b) {
    return a.c<b.c;
}
bool cmpv(Cake a, Cake b) {
    return a.v>b.v;
}
struct Node {
    int br;
    long long sum;
};
Cake a[MAXN], b[MAXN];
Node fen[MAXN];
int um[MAXN];
int n, m, max_st;
int curl, curr;
long long ans;
void update(int ind, int ch) {
    if (ind==0) return;
    ind=um[ind];
    long long pl;
    if (ch==1) pl=b[ind].v;
    else pl=-b[ind].v;
    while (ind<=n) {
        fen[ind].br+=ch;
        fen[ind].sum+=pl;
        ind+=(ind & (-ind));
    }
}
long long query(int ind) {
    long long res=0;
    while (ind>0) {
        res+=fen[ind].sum;
        ind-=(ind & (-ind));
    }
    return res;
}
long long findm(int k) {
    int st, ind;
    ind=max_st;
    st=(max_st>>1);
    while (st>0 && fen[ind].br!=k) {
        if (fen[ind].br>k) ind-=st;
        else {
            k-=fen[ind].br;
            while (ind+st>n) st=(st>>1);
            ind+=st;
        }
        st=(st>>1);
    }
    return query(ind);
}
void move_next(int nextl, int nextr) {
    while (curl>nextl) {
        update(curl-1,1);
        curl--;
    }
    while (curr<nextr) {
        update(curr+1,1);
        curr++;
    }
    while (curl<nextl) {
        update(curl,-1);
        curl++;
    }
    while (curr>nextr) {
        update(curr,-1);
        curr--;
    }
}
void dc(int l, int r, int opl, int opr) {
    if (l>r) return;
    int mid=(l+r)/2;
    int start=max(mid+m-1,opl), best=-1;
    long long res=-INF;
    move_next(mid+1,start-1);
    for (int i=start;i<=opr;i++) {
        long long s=findm(m-2)+a[mid].v+a[i].v-2ll*(a[i].c-a[mid].c);
        //cout << mid << ' ' << i << ' ' << s << ' ' << findm(m-2) << ' ' << a[mid].v+a[i].v << ' ' << 2*(a[i].c-a[mid].c) << endl;
        if (s>res) {
            res=s;
            best=i;
        }
        update(curr+1,1);
        curr++;
    }
    //cout << mid << ' ' << res << ' ' << best << ' ' << opl << ' ' << opr << endl;
    ans=max(ans,res);
    if (best==-1) return;
    dc(l,mid-1,opl,best);
    dc(mid+1,r,best,opr);
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i].v >> a[i].c;
    sort(a+1,a+n+1,cmpc);
    for (int i=1;i<=n;i++) {
        b[i]=a[i];
        b[i].ind=i;
    }
    sort(b+1,b+n+1,cmpv);
    for (int i=1;i<=n;i++) um[b[i].ind]=i;
    curl=curr=0;
    max_st=1;
    while (max_st<=n) max_st=(max_st<<1);
    max_st=(max_st>>1);
    ans=-INF;
    dc(1,n-m+1,1,n);
    cout << ans << endl;
    return 0;
}
/*
8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879
5 3
2 1
2 2
6 4
8 8
10 16
*/

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