Submission #389738

#	Time	Username	Problem	Language	Result	Execution time	Memory
389738		cgiosy	Cake 3 (JOI19_cake3)	C++17	100 / 100	660 ms	92400 KiB

cake3

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

struct cake {
	int v, x;
	bool operator<(cake b) const { return x<b.x; }
};
struct node {
	ll v; int c, l, r;
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, M;
	cin>>N>>M;
	cake A[N];
	int V[N];
	for(int i=0; i<N; i++) cin>>A[i].v>>A[i].x, V[i]=A[i].v;
	sort(A, A+N);
	sort(V, V+N);

	node T[3800100]{};
	int t=N;
	for(int i=0; i<N; i++) {
		int y=A[i].v, x=lower_bound(V, V+N, y)-V, p=i, q=i+1, s=0, e=N-1;
		while(s<e) {
			int m=s+e>>1;
			T[q].l=T[p].l, T[q].r=T[p].r;
			if(x<=m) T[q].v=T[p].v, T[q].c=T[p].c, e=m, p=T[p].l, q=T[q].l=++t;
			else T[q].v=T[p].v+y, T[q].c=T[p].c+1, s=m+1, p=T[p].r, q=T[q].r=++t;
		}
	}

	auto qry=[&](int l, int r) {
		int s=0, e=N-1, n=M;
		ll v=0;
		while(s<e) {
			int m=s+e>>1, c=T[r].c-T[l].c;
			if(n<=c) s=m+1, l=T[l].r, r=T[r].r;
			else v+=T[r].v-T[l].v, n-=c, e=m, l=T[l].l, r=T[r].l;
		}
		return v+ll(V[e])*n;
	};
	auto f=[&](int l, int r) {
		return qry(l, r)-2*(A[r-1].x-A[l].x);
	};

	ll ans=-1e18;
	function<void(int, int, int, int)> dnc=[&](int l, int r, int s, int e) {
		if(l>r || e-l<M) return;
		int m=l+r>>1, n=e;
		ll p=-1e18;
		for(int i=e; i>=max(s, m+M); i--) if(auto q=f(m, i); p<q) p=q, n=i;
		ans=max(ans, p);
		dnc(l, m-1, s, n), dnc(m+1, r, n, e);
	};
	dnc(0, N-1, M, N);
	cout<<ans<<'\n';
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:27:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |    int m=s+e>>1;
      |          ~^~
cake3.cpp: In lambda function:
cake3.cpp:38:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |    int m=s+e>>1, c=T[r].c-T[l].c;
      |          ~^~
cake3.cpp: In lambda function:
cake3.cpp:51:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int m=l+r>>1, n=e;
      |         ~^~

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