Submission #220610

#	Time	Username	Problem	Language	Result	Execution time	Memory
220610		atoiz	Cake 3 (JOI19_cake3)	C++14	100 / 100	474 ms	9720 KiB

cake3

/*input
8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const int MAXN = 200007, LOG = __lg(MAXN) + 1;
const int64_t INF = 1e17;

int64_t bit_sum[MAXN];
int bit_cnt[MAXN];
void add(int i, int64_t x)
{
	for (; i < MAXN; i += i & (-i)) bit_sum[i] += x, ++bit_cnt[i];
}

void rem(int i, int64_t x)
{
	for (; i < MAXN; i += i & (-i)) bit_sum[i] -= x, --bit_cnt[i];
}

int64_t get(int k)
{
	int64_t ans = 0;
	for (int i = 0, j = LOG - 1; j >= 0; --j) {
		if ((i | (1 << j)) < MAXN && bit_cnt[i | (1 << j)] <= k) {
			i |= (1 << j);
			k -= bit_cnt[i];
			ans += bit_sum[i];
		}
	}
	return ans;
}

int N, M;
int64_t ans = -INF;
int sortedC[MAXN], rankC[MAXN];
pair<int, int> cakes[MAXN];

int ptr_l = 0, ptr_r = -1;
int64_t calc(int l, int r)
{
	if (l + M - 1 > r) return -INF;
	while (ptr_l < l) rem(rankC[ptr_l], cakes[ptr_l].second), ++ptr_l;
	while (ptr_l > l) --ptr_l, add(rankC[ptr_l], cakes[ptr_l].second);
	while (ptr_r > r) rem(rankC[ptr_r], cakes[ptr_r].second), --ptr_r;
	while (ptr_r < r) ++ptr_r, add(rankC[ptr_r], cakes[ptr_r].second);
	return get(M) - 2ll * (cakes[r].first - cakes[l].first);
}

void solve(int opt_l, int opt_r, int l, int r)
{
	if (l > r) return;
	if (opt_l == opt_r) {
		for (int i = l; i <= r; ++i) ans = max(ans, calc(opt_l, i));
		return;
	}

	int m = (l + r) >> 1;
	int opt_m = opt_l;
	int64_t ans_m = calc(opt_m, m);
	for (int i = opt_l + 1; i <= opt_r; ++i) {
		int64_t cur = calc(i, m);
		if (cur > ans_m) {
			ans_m = cur;
			opt_m = i;
		}
	}

	ans = max(ans, ans_m);
	solve(opt_l, opt_m, l, m - 1);
	solve(opt_m, opt_r, m + 1, r);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		cin >> cakes[i].second >> cakes[i].first;
	}
	sort(cakes, cakes + N);

	iota(sortedC, sortedC + N, 0);
	sort(sortedC, sortedC + N, [&](int i, int j) { return cakes[i].second > cakes[j].second; });
	for (int i = 0; i < N; ++i) rankC[sortedC[i]] = i + 1;

	solve(0, N - 1, 0, N - 1);
	cout << ans << endl;
	return 0;
}

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