Submission #917564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
917564	2024-01-28T12:18:46 Z	y_combinator	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	197 ms	72960 KB

apple

#include <ios>
#include <iostream>
#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 solve() {

    const auto log2 = [](int x) {
        return 31 - __builtin_clz(x);
    };

    const auto sz = 1 << log2(MX * 2 - 1);

    auto m = 0;

    std::cin >> 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;
        std::cin >> 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);
            std::cout << 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 {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	7 ms	2848 KB	Output is correct
5	Correct	8 ms	3288 KB	Output is correct
6	Correct	8 ms	3164 KB	Output is correct
7	Correct	9 ms	3932 KB	Output is correct
8	Correct	55 ms	15984 KB	Output is correct
9	Correct	108 ms	26484 KB	Output is correct
10	Correct	117 ms	32028 KB	Output is correct
11	Correct	132 ms	33532 KB	Output is correct
12	Correct	118 ms	35092 KB	Output is correct
13	Correct	113 ms	39248 KB	Output is correct
14	Correct	116 ms	40704 KB	Output is correct
15	Correct	197 ms	70544 KB	Output is correct
16	Correct	162 ms	70652 KB	Output is correct
17	Correct	105 ms	41976 KB	Output is correct
18	Correct	116 ms	41444 KB	Output is correct
19	Correct	160 ms	72960 KB	Output is correct
20	Correct	179 ms	72132 KB	Output is correct