Submission #1014495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014495		vjudge1	Cake 3 (JOI19_cake3)	C++17	100 / 100	737 ms	106824 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
#define lolwhy(l,r) (qry(rt[l],rt[r+1],m)-2*cake[r].first+2*cake[l].first)
vector<pair<int,int>> cake;
struct node{
    int l,r,c;
    long long v;
} T[1<<22];
int rt[1<<18],CC,CV;
int nn1(int a,int b){
    T[++CC]={T[a].l,T[a].r,T[a].c+1,T[a].v+b};
    return CC;
}
int nn2(int a,int b){
    T[++CC]={a,b,T[a].c+T[b].c,T[a].v+T[b].v};
    return CC;
}
long long qry(int l,int r,int k){
    if(!r)return 0;
    if(T[r].c-T[l].c==k)
        return T[r].v-T[l].v;
    if(T[T[r].r].c-T[T[l].r].c>k)
        return qry(T[l].r,T[r].r,k);
    return qry(T[l].l,T[r].l,k-T[T[r].r].c+
        T[T[l].r].c)+T[T[r].r].v-T[T[l].r].v;
}
int ad(int i,int l,int r,int p,int v){
    if(l==r)return nn1(i,v);
    if(l+r>>1<p)return nn2(T[i].l,ad(T[i].r,l+r+2>>1,r,p,v));
    return nn2(ad(T[i].l,l,l+r>>1,p,v),T[i].r);
}
map<pair<int,int>,int>mp;
long long ans=-1e18;
void solve(int l,int r,int opl,int opr,int m){
    if(l>r)return;
    int mid=l+r>>1,op=0;
    long long cur=-1e18;
    for(int i=max(mid+m-1,opl);i<=opr;i++)
        if(lolwhy(mid,i)>cur)
            op=i,cur=lolwhy(mid,i);
    ans=max(ans,cur);
    solve(l,mid-1,opl,op,m);
    solve(mid+1,r,op,opr,m);
}
int main(){
    int n,m;
    cin>>n>>m;
    cake.resize(n);
    for(auto&[i,j]:cake)
        cin>>j>>i;
    sort(cake.begin(),cake.end());
    for(int i=0;i<n;i++)
        mp[{cake[i].second,i}];
    for(auto&[i,j]:mp)j=++CV;
    for(int i=0;i<n;i++)
        rt[i+1]=ad(rt[i],1,n,mp[{cake[i].second,i}],cake[i].second);
    solve(0,n-m,m-1,n-1,m);
    cout<<ans<<'\n';
}

Compilation message (stderr)

cake3.cpp: In function 'int ad(int, int, int, int, int)':
cake3.cpp:29:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     if(l+r>>1<p)return nn2(T[i].l,ad(T[i].r,l+r+2>>1,r,p,v));
      |        ~^~
cake3.cpp:29:48: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     if(l+r>>1<p)return nn2(T[i].l,ad(T[i].r,l+r+2>>1,r,p,v));
      |                                             ~~~^~
cake3.cpp:30:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     return nn2(ad(T[i].l,l,l+r>>1,p,v),T[i].r);
      |                            ~^~
cake3.cpp: In function 'void solve(int, int, int, int, int)':
cake3.cpp:36:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid=l+r>>1,op=0;
      |             ~^~

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