Submission #710264

#	Time	Username	Problem	Language	Result	Execution time	Memory
710264		LittleCube	Cake 3 (JOI19_cake3)	C++14	24 / 100	4022 ms	23264 KiB

cake3

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

int N, M;
ll ans = -1e18, dp[200005], v[200005], c[200005];
pii p[200005];

struct Mset
{
	vector<pair<int, ll>> op;
	multiset<ll> lms, rms;
	ll sum = 0;
	void init(int sz)
	{
		for(int i = 0; i < sz; i++)
			lms.insert(-10'000'000'000'000LL);
		sum = sz * -10'000'000'000'000LL;
	}	
	void insert(ll k)
	{
		lms.insert(k);
		op.emplace_back(pll(0, k));
		sum += k;
		rms.insert(*lms.begin());
		sum -= *lms.begin();
		op.emplace_back(pll(1, *lms.begin()));
		lms.erase(lms.begin());
	}
	void undo(int t)
	{
		while((int)op.size() > t)
		{
			auto [i, k] = op.back();
			op.pop_back();
			if(i == 0)
			{	
				lms.erase(lms.find(k));
				sum -= k;
			}
			else
			{
				rms.erase(rms.find(k));
				lms.insert(k);
				sum += k;
			}
		}
	}
}st;



// Assume (qR, L) is already in the set
void solve(int L, int R, int qL, int qR)
{
	int mid = (L + R) / 2;
	if(R < L)
		return;
	
	// cerr << L << ' ' << R << " -> " << qL << ' ' << qR << '\n'; 
	int initT = st.op.size();
	
	for (int i = mid - 1; i > qR && i >= L; i--)
		st.insert(v[i]);
	
	for (int i = min(mid - 1, qR); i >= qL; i--)
	{
		dp[i] = st.sum + v[mid] + v[i] - 2 * (c[mid] - c[i]);
		st.insert(v[i]);
	}

	st.undo(initT);

	int qMid = qL;
	for (int i = min(mid - 1, qR); i >= qL; i--)
		if(dp[i] >= dp[qMid])
			qMid = i;
	// cerr << mid << ' ' << qMid << ' ' << dp[qMid] << '\n';
	ans = max(dp[qMid], ans);

	for (int i = min(L - 1, qR); i > qMid; i--)
		st.insert(v[i]);

	solve(L, mid - 1, qL, qMid);

	st.undo(initT);

	for (int i = max(qR + 1, L); i <= mid; i++)
		st.insert(v[i]);

	solve(mid + 1, R, qMid, qR);

	st.undo(initT);
}	


signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	M -= 2;
	st.init(M);
	for(int i = 1; i <= N; i++)
		cin >> p[i].S >> p[i].F;
	sort(p + 1, p + 1 + N);
	for(int i = 1; i <= N; i++)
		c[i] = p[i].F, v[i] = p[i].S;
	solve(1, N, 1, N);
	cout << ans << '\n';
}

Compilation message (stderr)

cake3.cpp: In member function 'void Mset::undo(int)':
cake3.cpp:38:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |    auto [i, k] = op.back();
      |         ^

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