Submission #1102590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102590		imarn	Cake 3 (JOI19_cake3)	C++14	100 / 100	981 ms	205252 KiB

cake3

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
using namespace std;
const int mxn=2e5+5;
int n,k;
pll a[mxn];
vector<ll>v;
struct node{
    int val;ll tt;
    node *l,*r;
    node(int x,ll y) : val(x),tt(y),l(0),r(0){};
    node() : val(0),tt(0),l(0),r(0){};
    node(node *l,node *r) : val(l->val+r->val),tt(l->tt+r->tt),l(l),r(r){};
}*rt[mxn];
node* build(int l,int r){
    if(l==r)return new node();
    int m=(l+r)>>1;
    return new node(build(l,m),build(m+1,r));
}int sz;
node* upd(node *t,int l,int r,int idx,ll v){
    if(l==r){
        return new node(t->val+1,t->tt+v);
    }int m=(l+r)>>1;
    if(idx<=m)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=-2e16;
ll qr(node*tl,node*tr,int l,int r,ll x){
    if(l==r){
        return min(v[l-1]*x,tr->tt-tl->tt);
    }int m=(l+r)>>1;
    int idx=tr->r->val-tl->r->val;
    if(idx>=x)return qr(tl->r,tr->r,m+1,r,x);
    return tr->r->tt-tl->r->tt + qr(tl->l,tr->l,l,m,x-idx);
}
void solve(int l,int r,int opl,int opr){
    if(r<l)return;
    int m=(l+r)>>1;
    pll t={-2e16,-1};
    for(int i=opl;i<=min(m-k+1,opr);i++){
        t = max(t,{-2*a[m].f+2*a[i].f+qr(rt[i],rt[m-1],1,sz,k-2)+a[m].s+a[i].s,i});
    }ans=max(ans,t.f);if(l==r)return;
    if(t.s!=-1)solve(l,m-1,opl,t.s);
    if(t.s!=-1)solve(m+1,r,t.s,opr);
    else solve(m+1,r,opl,opr);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i].s>>a[i].f,v.pb(a[i].s);
    sort(a+1,a+n+1);sort(all(v));v.erase(unique(all(v)),v.end());sz=v.size();
    rt[0]=build(1,sz);
    for(int i=1;i<=n;i++)rt[i]=upd(rt[i-1],1,sz,upper_bound(all(v),a[i].s)-v.begin(),a[i].s);
    solve(1,n,1,n);cout<<ans;
}

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