Submission #530315

#	Time	Username	Problem	Language	Result	Execution time	Memory
530315		fhvirus	Cake 3 (JOI19_cake3)	C++17	100 / 100	2249 ms	17076 KiB

cake3

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

struct Lisan: vector<int> {
	void done() { sort(begin(), end()); erase(unique(begin(), end()), end()); }
	const int operator () (const int& v) const { return lower_bound(begin(), end(), v) - begin(); }
};
struct DS {
	int N, M, lp, rp;
	vector<int> val;
	Lisan lisan;
	vector<int64_t> sum;
	vector<int> cnt;
	DS (int _M): M(_M), val(1, 0) {}
	void add(const int& v) { lisan.emplace_back(v); val.emplace_back(v); }
	void build() {
		lisan.done();
		N = lisan.size();
		lp = 1; rp = 0;
		sum.assign(N * 4, 0ll);
		cnt.assign(N * 4, 0);
	}
	void modify(int i, int l, int r, int p, int v) {
		if (l + 1 == r) {
			sum[i] += lisan[p] * v;
			cnt[i] += v;
			return;
		}
		int m = (l + r) / 2;
		if (p < m) modify(i * 2, l, m, p, v);
		else modify(i * 2 + 1, m, r, p, v);
		sum[i] = sum[i * 2] + sum[i * 2 + 1];
		cnt[i] = cnt[i * 2] + cnt[i * 2 + 1];
		return;
	}
	int64_t query(int i, int l, int r, int k) {
		if (l + 1 == r)
			return (int64_t) lisan[l] * k;
		if (cnt[i] == k)
			return sum[i];
		int m = (l + r) / 2;
		if (cnt[i * 2 + 1] >= k)
			return query(i * 2 + 1, m, r, k);
		return sum[i * 2 + 1] + query(i * 2, l, m, k - cnt[i * 2 + 1]);
	}
	void clean() {
		for (int i = lp; i <= rp; ++i)
			modify(1, 0, N, lisan(val[i]), -1);
		lp = 1; rp = 0;
	}
	int64_t query(int l, int r) {
		if (l < lp) clean();
		while (rp < r) modify(1, 0, N, lisan(val[++rp]),  1);
		while (lp < l) modify(1, 0, N, lisan(val[lp++]), -1);
		return query(1, 0, N, M);
	}
};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, M; cin >> N >> M;
	vector<pair<int, int>> cakes(N + 1);
	for (int i = 1; i <= N; ++i)
		cin >> cakes[i].second >> cakes[i].first;

	sort(begin(cakes) + 1, end(cakes));

	DS ds(M);
	for (int i = 1; i <= N; ++i)
		ds.add(cakes[i].second);
	ds.build();

	int64_t ans = LLONG_MIN;

	queue<tuple<int, int, int, int>> q;
	q.emplace(1, N - M + 1, M, N);
	while (!q.empty()) {
		auto [l, r, sl, sr] = q.front(); q.pop();
		r = min(r, sr - M + 1);
		if (l > r) continue;
		int m = (l + r) / 2;
		int bests = -1;
		int64_t bestv = LLONG_MIN;
		for (int i = max(sl, m + M - 1); i <= sr; ++i) {
			int64_t val = ds.query(m, i) - 2ll * (cakes[i].first - cakes[m].first);
			if (val > bestv) {
				bests = i;
				bestv = val;
			}
		}
		ans = max(ans, bestv);
		if (l <= m - 1) q.emplace(l, m - 1, sl, bests);
		if (m + 1 <= r) q.emplace(m + 1, r, bests, sr);
	}

	cout << ans << '\n';

	return 0;
}

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