Submission #377278

#	Time	Username	Problem	Language	Result	Execution time	Memory
377278		jass921026	Cake 3 (JOI19_cake3)	C++14	100 / 100	3761 ms	27628 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef pair<int,int> pii;
#define F first
#define S second
const ll MAXN=2E5+10, INF=1E18;
int n, m, tmp[MAXN], pos[MAXN];
pii cake[MAXN];
ll ans[MAXN];
bool cmp(int a, int b){
    return cake[a].S<cake[b].S;
}
struct node{
    ll cnt=0, val=0;
    node* left=NULL;
    node* right=NULL;
    void pull(){
        cnt=left->cnt+right->cnt;
        val=left->val+right->val;
    }
    node(){};
    node(node* a, node* b){
        left=a, right=b;
        pull();
    }
};
node* root;
struct segment_tree{
    int L=0, R=-1;
    node* init(int l=0, int r=n-1){
        if(l==r) return new node();
        int mid=(l+r)/2;
        return new node(init(l,mid),init(mid+1,r));
    }
    void modify(int p, int v, node* now=root, int l=0, int r=n-1){
        if(l==r){
            now->cnt+=(v>0?1:-1);
            now->val+=v;
            return;
        }
        int mid=(l+r)/2;
        if(p<=mid) modify(p,v,now->left,l,mid);
        else modify(p,v,now->right,mid+1,r);
        now->pull();
    }
    ll query(int c=m, node* now=root, int l=0, int r=n-1){
        if(R-L+1<m) return -INF;
        if(c==0) return 0;
        if(c==now->cnt) return now->val;
        int mid=(l+r)/2;
        if(now->right->cnt<=c){
            return query(c-now->right->cnt,now->left,l,mid)+now->right->val;
        } else{
            return query(c,now->right,mid+1,r);
        }
    }
    void update(int l, int r){
        while(L>l){
            modify(pos[L-1],cake[L-1].S);
            L--;
        }
        while(R<r){
            modify(pos[R+1],cake[R+1].S);
            R++;
        }
        while(L<l){
            modify(pos[L],-cake[L].S);
            L++;
        }
        while(R>r){
            modify(pos[R],-cake[R].S);
            R--;
        }
    }
} sgt;
void solve(int l, int r, int ll, int rr){
    if(l>r) return;
    int mid=(l+r)/2, p=ll;
    long long penalty=0, sum=0;
    for(int i=ll;i<=rr;i++){
        if(i<mid) continue;
        penalty=2*(cake[i].F-cake[mid].F);
        sgt.update(mid,i);
        sum=sgt.query();
        //cout<<mid<<" "<<i<<" "<<sum<<" "<<penalty<<"\n";
        if(sum-penalty>ans[mid]){
            ans[mid]=sum-penalty;
            p=i;
        }
    }
    solve(l,mid-1,ll,p);
    solve(mid+1,r,p,rr);
}
int main(){ jizz
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>cake[i].S>>cake[i].F;
    }
    sort(cake,cake+n);
    for(int i=0;i<n;i++) tmp[i]=i;
    sort(tmp,tmp+n,cmp);
    for(int i=0;i<n;i++) pos[tmp[i]]=i;
    for(int i=0;i<n;i++) ans[i]=-INF;
    root=sgt.init();
    solve(0,n-m,0,n-1);
    ll ANS=-INF;
    for(int i=0;i<n;i++) ANS=max(ANS,ans[i]);
    cout<<ANS<<"\n";
    return 0;
}
/*
8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879
*/

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