Submission #331277

#	Time	Username	Problem	Language	Result	Execution time	Memory
331277		EIMONIM	Cake 3 (JOI19_cake3)	C++14	100 / 100	1380 ms	18692 KiB

cake3

#include <bits/stdc++.h>
#define int int64_t
#define vi vector<int>
#define ii pair<int,int>
#define vb vector<bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vii vector<ii>
#define vvii vector<vii>
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
using namespace std;
const int INF = 1e18, MOD = 1e9 + 7;


const int MAXN = 2e5+10;
struct Seg{
    int sz;
    vi a, amt, v;
    void init(int n){
        for(sz=1;sz<n;sz*=2);
        a.resize(2*sz);
        amt.resize(2*sz);
    }
    void update(int i, bool b){
        i+=sz;
        amt[i] = b;
        a[i] = v[i-sz] * b;
        for(i/=2; i; i/=2) a[i] = a[2*i] + a[2*i+1], amt[i] = amt[2*i] + amt[2*i+1];
    }
    int query(int k){
        if (amt[1]<k) return -INF;
        int res = 0, i = 1;
        for(; i<sz; ){
            //cout<<"AMT: "<<i<<" : "<<k<<" "<<amt[i]<<" "<<amt[2*i]<<" "<<amt[2*i+1]<<endl;
            if (amt[2*i]<=k) k-=amt[2*i], res+=a[2*i], i = 2*i+1;
            else i = 2*i;
        }
        if (k) res+=a[i], k--;
        //cout<<"K: "<<k<<endl;
        assert(k==0);
        return res;
    }
} seg;
int n,m;
ii a[MAXN];
int ll=0,rr=-1;
int res = 0;
int back[MAXN];
void update(int aa, int bb){
    if (aa > rr || bb < ll){
        while(ll<=rr) seg.update(back[ll++], 0);
        ll = aa, rr = aa-1;
    }
    while(bb>rr) seg.update(back[++rr],1);
    while(aa<ll) seg.update(back[--ll],1);
    while(bb<rr) seg.update(back[rr--],0);
    while(aa>ll) seg.update(back[ll++],0);
}
int ans = -INF;
void solve(int l, int r, int optl, int optr){
    if (r<l) return ;
    int i = (l+r)/2;
    int opt = optr, bestv = -INF/2;
    loop(j,max(optl, i+m-1),optr+1){
        update(i, j);
        int v = seg.query(m) - (a[j].x - a[i].x);
        if (bestv < v){
            bestv = v;
            opt = j;
        }
    }
    chkmax(ans, bestv);
    solve(i+1, r, opt, optr);
    solve(l, i-1, optl, opt);
}
 
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    vii vals(n);
    loop(i,0,n) cin>>a[i].y>>a[i].x, a[i].x*=2;
    sort(a, a+n);
    loop(i,0,n) vals[i] = {a[i].y, i};
    sort(all(vals));
    reverse(all(vals));
    seg.init(n);
    loop(i,0,n) seg.v.pb(vals[i].x), back[vals[i].y] = i;
    solve(0,n-m,m-1,n-1);
    cout<<ans<<endl;
    return 0;
}
/*
color a
cls
g++ cake3.cpp -o a & a
5 3
2 1
4 2
6 4
8 8
10 16



*/

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