Submission #229106

#	Time	Username	Problem	Language	Result	Execution time	Memory
229106		kig9981	Cake 3 (JOI19_cake3)	C++17	100 / 100	1345 ms	137980 KiB

cake3

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct PST
{
	int l, r, c;
	long long s;
	PST() : l(0), r(0), c(0), s(0) {}
};

const int SZ=1<<18;
int N, M, node_cnt;
pair<int,int> C[200000], x[200000];
PST tree[5555555];
long long ans=-0x7fffffffffffffffLL;

void set_tree(int b, int n, int v, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) {
		tree[p].s=v;
		tree[p].c=1;
		return;
	}
	if(n<=m) {
		tree[p].l=node_cnt++;
		tree[p].r=tree[b].r;
		set_tree(tree[b].l,n,v,tree[p].l,s,m);
	}
	else {
		tree[p].r=node_cnt++;
		tree[p].l=tree[b].l;
		set_tree(tree[b].r,n,v,tree[p].r,m+1,e);
	}
	tree[p].s=tree[tree[p].l].s+tree[tree[p].r].s;
	tree[p].c=tree[tree[p].l].c+tree[tree[p].r].c;
}

int kth(int l, int r, int k)
{
	int s=0, e=SZ-1;
	while(s<e) {
		int m=(s+e)>>1;
		if(tree[tree[r].l].c-tree[tree[l].l].c>=k) {
			l=tree[l].l;
			r=tree[r].l;
			e=m;
		}
		else {
			k-=tree[tree[r].l].c-tree[tree[l].l].c;
			l=tree[l].r;
			r=tree[r].r;
			s=m+1;
		}
	}
	return s;
}

long long get_sum(int n1, int n2, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(p==0 || n2<n1 || n2<s || e<n1) return 0;
	if(n1<=s && e<=n2) return tree[p].s;
	return get_sum(n1,n2,tree[p].l,s,m)+get_sum(n1,n2,tree[p].r,m+1,e);
}

void solve(int s1, int e1, int s2, int e2)
{
	int m1=(s1+e1)>>1, m2=-1;
	long long mx=-0x7fffffffffffffffLL, t;
	if(s1>e1) return;
	for(int i=max(s2,m1+M-1);i<=e2;i++) {
		int k=kth(m1,i+1,M);
		if((t=get_sum(0,k,i+1)-get_sum(0,k,m1)-2LL*(C[i].first-C[m1].first))>=mx) {
			mx=t;
			m2=i;
		}
	}
	ans=max(ans,mx);
	solve(s1,m1-1,s2,m2);
	solve(m1+1,e1,m2,e2);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	cin>>N>>M; node_cnt=N+1;
	for(int i=0;i<N;i++) cin>>C[i].second>>C[i].first;
	sort(C,C+N);
	for(int i=0;i<N;i++) x[i]={C[i].second,i};
	sort(x,x+N);
	for(int i=0;i<N;i++) C[x[i].second].second=i;
	for(int i=0;i<N;i++) set_tree(i,N-C[i].second,x[C[i].second].first,i+1);
	solve(0,N-M,M-1,N-1);
	cout<<ans<<'\n';
	return 0;
}

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