Submission #1012446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012446		imarn	Cake 3 (JOI19_cake3)	C++14	100 / 100	862 ms	208260 KiB

cake3

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
#define ub(x,y) upper_bound(all(y),x)-y.begin()
using namespace std;
const int mxn=2e5+5;
struct node{
    ll a,b;
    node*l,*r;
    node (int a,ll b):a(a),b(b),l(NULL),r(NULL){};
    node (node *l,node *r):a(l->a+r->a),b(l->b+r->b),l(l),r(r){};
}*rt[mxn];
int N,M,sz;
ll v[mxn],c[mxn];
vector<ll>g;
node* build(int l,int r){
    if(l==r)return new node(0,0);
    int m=(l+r)>>1;
    return new node(build(l,m),build(m+1,r));
}
node *upd(node*t,int l,int r,int idx,ll v){
    if(l==r)return new node(t->a+1,t->b+v);
    int m=(l+r)>>1;
    if(m>=idx)return new node(upd(t->l,l,m,idx,v),t->r);
    else return new node(t->l,upd(t->r,m+1,r,idx,v));
}ll ans=-1e16;
ll qr(node *tl,node *tr,int l,int r,int k){
    if(l==r){
        return min(tr->b-tl->b,1ll*k*g[l-1]);
    }int m=(l+r)>>1;int idx=tr->r->a-tl->r->a;
    if(idx>=k)return qr(tl->r,tr->r,m+1,r,k);
    else return tr->r->b-tl->r->b+qr(tl->l,tr->l,l,m,k-idx);
}
void solve(int l,int r,int opl,int opr){
    if(r<l)return;
    int m=(l+r)>>1;
    pair<ll,ll>t={-1e16,0};
    for(int i=opl;i<=min(opr,m-1);i++){
        if(m-i+1<M)break;
        ll rs=-2*c[m]+2*c[i]+qr(rt[i],rt[m-1],1,sz,M-2)+v[m]+v[i];
        t=max(t,{rs,i});
    }ans=max(ans,t.f);
    if(t.s==0)solve(l,m-1,opl,opr);
    else solve(l,m-1,opl,t.s);
    if(t.s==0)solve(m+1,r,opl,opr);
    else solve(m+1,r,t.s,opr);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>N>>M;vector<pair<ll,ll>>tmp;
    for(int i=0;i<N;i++){
        int x,y;cin>>x>>y;
        tmp.pb({y,x});g.pb(x);
    }sort(all(tmp));sort(all(g));g.erase(unique(all(g)),g.end());
    for(int i=0;i<N;i++)v[i+1]=tmp[i].s,c[i+1]=tmp[i].f;sz=g.size();
    rt[0]=build(1,sz);
    for(int i=1;i<=N;i++)rt[i]=upd(rt[i-1],1,sz,ub(v[i],g),v[i]);
    solve(1,N,1,N);cout<<ans;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:59:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   59 |     for(int i=0;i<N;i++)v[i+1]=tmp[i].s,c[i+1]=tmp[i].f;sz=g.size();
      |     ^~~
cake3.cpp:59:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   59 |     for(int i=0;i<N;i++)v[i+1]=tmp[i].s,c[i+1]=tmp[i].f;sz=g.size();
      |                                                         ^~

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