제출 #1174212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174212		betvoi	Cake 3 (JOI19_cake3)	C++20	24 / 100	4094 ms	3520 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;
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);
}
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);
    });
    ll ans=-1e18;
    For(i,1,n-m+1) {
        For(j,1,n) rem(a[j].ff,j);
        For(j,i,n) {
            ll dis=2LL*(a[j].ss-a[i].ss);
            add(a[j].ff,j);
            if (siz>=m) ans=max(ans,sm-dis);
        }
    }
    cout << ans;
    return 0;
}

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