Submission #948271

#	Time	Username	Problem	Language	Result	Execution time	Memory
948271		pcc	Cake 3 (JOI19_cake3)	C++17	0 / 100	26 ms	145284 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2e5+10;
vector<int> all;

struct node{
	int pl,pr,cnt;
	ll sum;
	node(){
		pl = pr = cnt = sum = 0;
	}
};
const int SZ = mxn*30;
node seg[SZ];
int ppp = 0;

int newnode(int src){
	ppp++;
	assert(ppp<SZ);
	seg[ppp] = seg[src];
	return ppp;
}

#define mid ((l+r)>>1)
int modify(int now,int l,int r,int p,int v){
	now = newnode(now);
	if(l == r){
		seg[now].cnt++;
		seg[now].sum += v;
		return now;
	}
	if(mid>=p)seg[now].pl = modify(seg[now].pl,l,mid,p,v);
	else seg[now].pr = modify(seg[now].pr,mid+1,r,p,v);
	seg[now].sum = seg[seg[now].pl].sum+seg[seg[now].pr].sum;
	seg[now].cnt = seg[seg[now].pl].cnt+seg[seg[now].pr].cnt;
	return now;
}
ll getval(int s,int e,int l,int r,int tar){
	if(l == r){
		return 1ll*all[l]*min(seg[e].cnt-seg[s].cnt,tar);
	}
	if(seg[seg[e].pr].cnt-seg[seg[s].pr].cnt>=tar)return getval(seg[s].pr,seg[e].pr,mid+1,r,tar);
	else return getval(seg[s].pl,seg[e].pl,l,mid,tar-(seg[seg[e].pr].cnt-seg[seg[s].pr].cnt))+seg[seg[e].pr].sum-seg[seg[s].pr].sum;
}
#undef mid

int rt[mxn];
pii arr[mxn];
int N,M;
ll ans[mxn];

ll calc(int a,int b){
	auto re = getval(rt[a],rt[b],0,all.size(),M)+arr[a+1].fs*2-arr[b].fs*2;
	return re;
}

void dc(int ql,int qr,int opl,int opr){
	int mid = (ql+qr)>>1;
	int opt = opl;
	ll val = calc(opl,ql);
	for(int i = opl;i<=min(mid-M,opr);i++){
		auto tmp = calc(i,mid);
		if(tmp>=val)val = tmp,opt = i;
	}
	ans[mid] = val;
	if(ql != mid)dc(ql,mid-1,opl,opt);
	if(qr != mid)dc(mid+1,qr,opt,opr);
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(auto &i:ans)i = -1e18;
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		cin>>arr[i].sc>>arr[i].fs;
		all.push_back(arr[i].sc);
	}
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	sort(arr+1,arr+N+1);
	for(int i = 1;i<=N;i++){
		arr[i].sc = lower_bound(all.begin(),all.end(),arr[i].sc)-all.begin();
		rt[i] = modify(rt[i-1],0,all.size(),arr[i].sc,all[arr[i].sc]);
	}
	//cout<<seg[rt[N]].sum<<":"<<seg[rt[N]].cnt<<' '<<getval(rt[0],rt[3],0,all.size(),M)<<endl;
	dc(M,N,0,N);
	cout<<*max_element(ans+M,ans+N+1);
}

Compilation message (stderr)

cake3.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main(){
      | ^~~~

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