Submission #710279

#	Time	Username	Problem	Language	Result	Execution time	Memory
710279		Darren0724	Cake 3 (JOI19_cake3)	C++17	100 / 100	1037 ms	242248 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define x first
#define y second
const long long INF=1e18;
const int N=200005;
int n,m;
int cnta=0;
vector<int> lisan;
vector<pair<int,int>> v;
struct seg{
    int l,m,r;
    seg *lc,*rc;
    long long cnt=0,total=0;
    seg(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        lc=rc=NULL;
        cnta++;
    }
    void pull(){
        cnt=0;
        total=0;
        if(lc){
            cnt+=lc->cnt;
            total+=lc->total;
        }
        if(rc){
            cnt+=rc->cnt;
            total+=rc->total;
        }
    }
    void add(int p){
        if(r-l==1){
            cnt++;
            total+=lisan[p];
            return;
        }
        m=(l+r)>>1;
        if(p<m){
            lc=(lc?new seg(*lc):new seg(l,m));
            lc->add(p);
        }
        else{
            rc=(rc?new seg(*rc):new seg(m,r));
            rc->add(p);
        }
        pull();
    }
};
vector<seg*> tr;
long long total(seg* s){
    return s?s->total:0;
}
int cnt(seg* s){
    return s?s->cnt:0;
}
seg* lc(seg* s){
    return s?s->lc:NULL;
}
seg* rc(seg* s){
    return s?s->rc:NULL;
}
long long ask(seg* a,seg* b,int need,int l,int r){
    //cout<<l<<' '<<r<<endl;
    if(r-l==1){
        return (need>cnt(b)-cnt(a)?-INF:need*lisan[l]);
    }
    int m=(l+r)>>1;
    if(cnt(rc(b))-cnt(rc(a))>=need){
        return ask(rc(a),rc(b),need,m,r);
    }
    else{
        return total(rc(b))-total(rc(a))+ask(lc(a),lc(b),need-cnt(rc(b))+cnt(rc(a)),l,m);
    }
}
long long ans1=-INF;
void dc(int l,int r,int a,int b){
    //cout<<l<<' '<<r<<endl;
    if(l>=r){
        return;
    }
    pair<long long,int> p={-INF,-1};
    int m1=(l+r)>>1;
    for(int i=a;i<=min(b,m1-1);i++){
        p=max(p,{ask(tr[i],tr[m1],m,0,N)-(v[m1].x-v[i+1].x)*2,i});
        //cout<<m1<<' '<<i<<endl;
    }
    ans1=max(ans1,p.first);
    dc(l,m1,a,p.second);
    dc(m1+1,r,p.second,b);
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    v.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i].y>>v[i].x;
        //v[i].x=100+i*5720;
        //v[i].y=100019+i*2729;
        //lisan.push_back(v[i].x);
        lisan.push_back(v[i].y);
    }
    sort(all(lisan));
    lisan.resize(unique(all(lisan))-lisan.begin());
    for(int i=1;i<=n;i++){
        v[i].y=lower_bound(all(lisan),v[i].y)-lisan.begin();
    }
    sort(v.begin(),v.end());
    tr.resize(n+1);
    tr[0]=new seg(0,N);
    for(int i=1;i<=n;i++){
        tr[i]=new seg(*tr[i-1]);
        tr[i]->add(v[i].y);
    }
    int idx=0;
    dc(m,n+1,0,n);
    cout<<ans1<<endl;
    //cout<<cnta<<endl;

    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int32_t main()':
cake3.cpp:118:9: warning: unused variable 'idx' [-Wunused-variable]
  118 |     int idx=0;
      |         ^~~

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