QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1145 | #712344 | #9588. 可重集合 | Grenier | xhgua | Failed. | 2024-11-07 17:31:24 | 2024-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
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#712344 | #9588. 可重集合 | xhgua# | AC ✓ | 463ms | 7000kb | C++17 | 1.3kb | 2024-11-05 15:23:36 | 2024-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;
}