#include <fstream>
#include <utility>
#include <vector>
struct Node {
int cnt = 0;
bool set = false;
int node_l = -1;
int node_r = -1;
};
template <typename F>
class YCombinator {
private:
const F f = nullptr;
public:
explicit YCombinator(F&& f) : f(f) {}
template <typename... Ts>
decltype(auto) operator()(Ts&&... arguments) const {
return f(*this, std::forward<Ts>(arguments)...);
}
};
template <typename F>
YCombinator(F) -> YCombinator<F>;
constexpr auto MX = 1'000'000'000;
auto fin = std::ifstream("f.in");
auto fout = std::ofstream("f.out");
auto solve() {
const auto log2 = [](int x) {
return 31 - __builtin_clz(x);
};
const auto sz = 1 << log2(MX * 2 - 1);
auto m = 0;
fin >> m;
auto c = 0;
auto nodes = std::vector<Node>(1);
nodes.reserve(m * (log2(sz) + 1) << 2);
for (auto i = 0; i < m; ++i) {
auto d = 0;
auto x = 0;
auto y = 0;
fin >> d >> x >> y;
x += c;
y += c;
const auto apply = [](Node& node, int sz) {
node.cnt = sz;
node.set = true;
};
const auto check = [&](int& node) {
if (node != -1) {
return;
}
nodes.emplace_back();
node = nodes.size() - 1;
};
const auto push = [&](Node& node, int sz) {
if (!node.set) {
return;
}
apply(nodes[node.node_l], sz >> 1);
apply(nodes[node.node_r], sz >> 1);
node.set = false;
};
if (d == 1) {
c = 0;
YCombinator(
[&](auto self, Node& node, int idx_l, int idx_r, int tree_l, int tree_r) {
if (idx_l == tree_l && idx_r == tree_r) {
c += node.cnt;
return;
}
auto& [cnt, set, node_l, node_r] = node;
check(node_l);
check(node_r);
push(node, tree_r - tree_l);
const auto tree_m = (tree_l + tree_r) >> 1;
if (idx_l < tree_m) {
self(nodes[node_l], idx_l, std::min(idx_r, tree_m), tree_l, tree_m);
}
if (idx_r > tree_m) {
self(nodes[node_r], std::max(idx_l, tree_m), idx_r, tree_m, tree_r);
}
}
)(nodes[0], x, y + 1, 0, sz);
fout << c << '\n';
} else {
YCombinator(
[&](auto self, Node& node, int idx_l, int idx_r, int tree_l, int tree_r) {
if (idx_l == tree_l && idx_r == tree_r) {
apply(node, idx_r - idx_l);
return;
}
auto& [cnt, set, node_l, node_r] = node;
check(node_l);
check(node_r);
push(node, tree_r - tree_l);
const auto tree_m = (tree_l + tree_r) >> 1;
if (idx_l < tree_m) {
self(nodes[node_l], idx_l, std::min(idx_r, tree_m), tree_l, tree_m);
}
if (idx_r > tree_m) {
self(nodes[node_r], std::max(idx_l, tree_m), idx_r, tree_m, tree_r);
}
cnt = nodes[node_l].cnt + nodes[node_r].cnt;
}
)(nodes[0], x, y + 1, 0, sz);
}
}
}
auto main() -> int {
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
