Submission #406039

#	Time	Username	Problem	Language	Result	Execution time	Memory
406039		ansol4328	Cake 3 (JOI19_cake3)	C++14	100 / 100	956 ms	91868 KiB

cake3

#include<bits/stdc++.h>
#define rs resize

using namespace std;
typedef long long ll;

struct A{
    int x, y, v;
};

bool cmp1(const A &lhs, const A &rhs){
    return lhs.x<rhs.x;
}

bool cmp2(const A &lhs, const A &rhs){
    return lhs.v>rhs.v;
}

struct PST{
    vector<int> cnt, left, right, root;
    vector<ll> sum;
    int base, t;
    PST(int w, int rt, int up){
        int h=1; base=t=1;
        while(base<w) base<<=1, h++;
        int x=base*2+up*h+5;
        cnt.rs(x); sum.rs(x);
        left.rs(x); right.rs(x);
        root.rs(rt+5);
        root[0]=setUp(1,base);
    }
    int setUp(int l, int r){
        int cur=t++;
        if(l<r){
            int mid=(l+r)>>1;
            left[cur]=setUp(l,mid);
            right[cur]=setUp(mid+1,r);
        }
        return cur;
    }
    void updateKthTree(int k, int idx, int val){
        if(!root[k]) root[k]=root[k-1];
        root[k]=addNode(root[k],idx,val,1,base);
    }
    int addNode(int prev, int idx, int val, int l, int r){
        if(r<idx || idx<l) return prev;
        int cur=t++;
        if(l==r) cnt[cur]=1, sum[cur]=val;
        else{
            int mid=(l+r)>>1;
            left[cur]=addNode(left[prev],idx,val,l,mid);
            right[cur]=addNode(right[prev],idx,val,mid+1,r);
            l=left[cur], r=right[cur];
            sum[cur]=sum[l]+sum[r];
            cnt[cur]=cnt[l]+cnt[r];
        }
        return cur;
    }
    ll qry(int i1, int i2, int k){
        return qry(root[i1],root[i2],k,1,base);
    }
    ll qry(int i1, int i2, int k, int l, int r){
        if(k<=0) return 0LL;
        if(cnt[i1]-cnt[i2]<=k) return sum[i1]-sum[i2];
        int mid=(l+r)>>1;
        int x=cnt[left[i1]]-cnt[left[i2]];
        return qry(left[i1],left[i2],k,l,mid)+qry(right[i1],right[i2],k-x,mid+1,r);
    }
};

int N, M;
A VC[200005];
PST *pst;
ll ans;
const ll INF=1e18;

void solve(int l, int r, int optl, int optr)
{
    if(l>r) return;
    int j=(l+r)>>1, opt=optl; ll v=-INF;
    for(int i=max(optl,j+M-1) ; i<=optr ; i++){
        ll val=pst->qry(i,j-1,M)-2LL*(VC[i].x-VC[j].x);
        if(v<val) v=val, opt=i;
    }
    ans=max(ans,v);
    solve(l,j-1,optl,opt);
    solve(j+1,r,opt,optr);
}

int main()
{
    scanf("%d %d",&N,&M);
    for(int i=1 ; i<=N ; i++){
        scanf("%d %d",&VC[i].v,&VC[i].x);
    }
    sort(VC+1,VC+1+N,cmp2);
    for(int i=1 ; i<=N ; i++) VC[i].y=i;
    sort(VC+1,VC+1+N,cmp1);
    
    ans=-INF;
    pst=new PST(N,N,N);
    for(int i=1 ; i<=N ; i++) pst->updateKthTree(i,VC[i].y,VC[i].v);
    solve(1,N-M+1,1,N);
    delete pst;
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d %d",&VC[i].v,&VC[i].x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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