QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1145#712344#9588. 可重集合GrenierxhguaFailed.2024-11-07 17:31:242024-11-07 17:31:24

Details

Extra Test:

Accepted
time: 1ms
memory: 4020kb

input:

2
1 1
2 1

output:

1
0

result:

ok 2 lines

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#712344#9588. 可重集合xhgua#AC ✓463ms7000kbC++171.3kb2024-11-05 15:23:362024-11-05 15:23:38

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int B = 700;
constexpr int N = 500005;
using Bitset = std::bitset<N>;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;

	std::vector<std::vector<int>> seg(4 * n);

	auto rangeApply = [&](auto &&self, int p, int l, int r, int x, int y, int s) -> void {
		if (x <= l && r <= y) {
			seg[p].push_back(s);
			return ;
		}
		int m = (l + r) / 2;
		if (x < m) {
			self(self, 2 * p, l, m, x, y, s);
		}
		if (m < y) {
			self(self, 2 * p + 1, m, r, x, y, s);
		}
	};
	
	std::map<int, std::vector<int>> mp;
	for (int i = 0; i < n; i++) {
		int op, x;
		std::cin >> op >> x;
		if (op == 2) {
			int p = mp[x].back();
			mp[x].pop_back();
			rangeApply(rangeApply, 1, 0, n, p, i, x);
		} else {
			mp[x].push_back(i);
		}
	}
	for (auto &[x, v] : mp) {
		for (int p : v) {
			rangeApply(rangeApply, 1, 0, n, p, n, x);
		}
	}

	auto dfs = [&](auto &&self, int p, int l, int r, Bitset &s) -> void {
		Bitset ns = s;
		for (int x : seg[p]) {
			ns |= (ns << x);
		}
		if (l + 1 < r) {
			int m = (l + r) / 2;
			self(self, 2 * p, l, m, ns);
			self(self, 2 * p + 1, m, r, ns);
		} else {
			std::cout << ns.count() - 1 << "\n";
		}
	};
	Bitset b{};
	b[0] = 1;
	dfs(dfs, 1, 0, n, b);

	return 0;
}