제출 #1174222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174222		betvoi	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	328 KiB

cake3

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int N=2e5+3;

int n,m,pf[N],siz=0;
bool ski[N];
pair<int,int> a[N];
ll sm=0,ans[N];
vector<int> big;

void update(int x,int y) {
    if (x==0) return;
    siz+=y;
    while(x<=n) {
        pf[x]+=y;
        x+=x&(-x);
    }
}
int query(int x) {
    int ans=0;
    while(x>0) {
        ans+=pf[x];
        x-=x&(-x);
    }
    return ans;
}
int find_n(int x) {
    int idx=0,cur=0;
    ForD(i,17,0)
        if (idx+(1<<i)<=n && cur+pf[idx+(1<<i)]<x) {
            idx+=1<<i;
            cur+=pf[idx];
        }
    return idx+1;
}
void add(int x,int idx) {
    if (ski[idx]) return;
    ski[idx]=1;
    int tmp=siz-query(x-1);
    if (siz<m || tmp<m) {
        sm+=big[x-1];
        if (siz>=m) {
            int idx=find_n(siz-m+1);
            sm-=big[idx-1];
        }
    }
    update(x,1);
}
void rem(int x,int idx) {
    if (!ski[idx]) return;
    ski[idx]=0;
    int tmp=siz-query(x-1);
    if (tmp<=m) {
        sm-=big[x-1];
        if (siz>m) {
            int huhu=find_n(siz-m);
            sm+=big[huhu-1];
        }
    }
    update(x,-1);
}
void solve(int l,int r,int lo,int hi) {
    if (l>r) return;
    int mid=l+r>>1;
    For(i,mid,min(r,lo-1)) add(a[i].ff,i);
    int opt=-1;
    ans[mid]=-1e18;
    For(i,max(mid,lo),hi) {
        add(a[i].ff,i);
        ll dis=2LL*(a[i].ss-a[mid].ss);
        if (siz>=m && ans[mid]<sm-dis) {
            // if (mid==5 && i==5) {
            //     For(j,1,n) cout << ski[j] << " ";
            //     cout << endl;
            // }
            opt=i;
            ans[mid]=sm-dis;
        }
    }
    // if (opt==-1) opt=mid;
    // debug(l,r,lo,hi,mid,opt);
    // cout << mid << " " << lo << " " << hi << endl;
    // For(i,1,n) cout << ski[i] << " ";
    // cout << endl;
    // debug(mid,opt);
    For(i,max(mid,lo),hi) rem(a[i].ff,i);
    solve(l,mid-1,lo,opt);
    For(i,mid,min(r,lo-1)) rem(a[i].ff,i);
    For(i,max(r+1,lo),opt-1) add(a[i].ff,i);
    solve(mid+1,r,opt,hi);
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    For(i,1,n) {
        cin >> a[i].ff >> a[i].ss;
        big.pb(a[i].ff);
    }
    sort(all(big));
    unq(big);
    For(i,1,n) a[i].ff=(lower_bound(all(big),a[i].ff)-big.begin())+1;
    sort(a+1,a+1+n,[=](const pair<int,int> A,const pair<int,int> B){
        return make_pair(A.ss,A.ff)<make_pair(B.ss,B.ff);
    });
    solve(1,n-m+1,1,n);
    ll res=*max_element(ans+1,ans+n-m+2);
    cout << res;
    return 0;
}

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