Submission #709952

#	Time	Username	Problem	Language	Result	Execution time	Memory
709952		victor_gao	Cake 3 (JOI19_cake3)	C++17	100 / 100	1051 ms	210948 KiB

cake3

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,ans=-1e18;
pii arr[N];
struct Node{
    int lch,rch,sum,cnt;
    void pull(Node a,Node b){
        sum=a.sum+b.sum;
        cnt=a.cnt+b.cnt;
    }
    Node(int a=0,int b=0,int c=0,int d=0):lch(a),rch(b),sum(c),cnt(d){}
};
struct lisan{
    vector<int>vt;
    void in(int x){ vt.push_back(x); }
    void build(){
        sort(vt.begin(),vt.end());
        vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    }
    int idx(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
    int val(int p){ return vt[p-1]; }
}uni;

struct segtree{
    int num=1;
    Node seg[32*N];
    int add(int l,int r,int i,int pos,int c){
        num++; seg[num]=seg[i];
        if (l==r){
            seg[num].cnt++;
            seg[num].sum+=uni.val(l);
            return num;
        }
        int mid=(l+r)>>1,j=num;
        if (pos<=mid) seg[j].lch=add(l,mid,seg[i].lch,pos,c);
        else seg[j].rch=add(mid+1,r,seg[i].rch,pos,c);
        seg[j].pull(seg[seg[j].lch],seg[seg[j].rch]);
        return j;
    }
    int query_pos(int l,int r,int i,int j,int k){
        if (l==r) return l;
        int mid=(l+r)>>1,rc1=seg[i].rch,rc2=seg[j].rch;
        int right_have=seg[rc2].cnt-seg[rc1].cnt;
        if (right_have>=k) return query_pos(mid+1,r,rc1,rc2,k);
        else return query_pos(l,mid,seg[i].lch,seg[j].lch,k-right_have);
    }
    Node query(int l,int r,int i,int j,int ll,int rr){
        // seg[j]-seg[i];
        if (ll<=l&&rr>=r) return Node(0,0,seg[j].sum-seg[i].sum,seg[j].cnt-seg[i].cnt);
        int mid=(l+r)>>1;
        if (rr<=mid) return query(l,mid,seg[i].lch,seg[j].lch,ll,rr);
        else if (ll>mid) return query(mid+1,r,seg[i].rch,seg[j].rch,ll,rr);
        else {
            Node q1=query(l,mid,seg[i].lch,seg[j].lch,ll,rr);
            Node q2=query(mid+1,r,seg[i].rch,seg[j].rch,ll,rr);
            Node ans=Node(); ans.pull(q1,q2);
            return ans;
        }
    }
}seg;
int root[N];
int Query(int l,int r){
    if (r-l+1<m) return -1e18;
    int p=seg.query_pos(1,n,root[l-1],root[r],m),val=uni.val(p);
    Node now=seg.query(1,n,root[l-1],root[r],p,n);
    if (now.cnt>m){
        now.sum=(now.sum-(now.cnt-m)*val);
        now.cnt=m;
    }
    return now.sum-2*(arr[r].y-arr[l].y);
}
void Merge(int l,int r,int ql,int qr){
    if (ql>qr) return;
    if (l==r){
        for (int i=ql;i<=qr;i++)
            ans=max(ans,Query(l,i));
        return;
    }
    int mid=(ql+qr)>>1,best=-1e18,from=l;
    for (int i=l;i<=r;i++){
        int c=Query(i,mid);
        if (c>best){
            best=c;
            from=i;
        }
    }
    ans=max(ans,best);
    Merge(l,from,ql,mid-1);
    Merge(from,r,mid+1,qr);
}

bool cmp(pii a,pii b){
    if (a.y!=b.y) return a.y<b.y;
    return a.x<b.x;
}
signed main(){
    fast
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>arr[i].x>>arr[i].y;
        uni.in(arr[i].x);
    }
    uni.build();
    for (int i=1;i<=n;i++)
        arr[i].x=uni.idx(arr[i].x);
    sort(arr+1,arr+1+n,cmp);
    for (int i=1;i<=n;i++){
        root[i]=seg.add(1,n,root[i-1],arr[i].x,1);
    }
    Merge(1,n,m,n);
    cout<<ans<<'\n';
}

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