Submission #917562

#	Time	Username	Problem	Language	Result	Execution time	Memory
917562		y_combinator	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	0 ms	348 KiB

apple

#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;

}

• Subtask 1: 0 / 100