Submission #1177579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177579		Pannda	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	233 ms	83092 KiB

apple

#include <bits/stdc++.h>
using namespace std;

template <class Info, class Tag>
struct ImplitcitLazySegmentTree {
    struct Node {
        Info info = Info();
        Tag tag = Tag();
        int ln = 0, rn = 0;
    };

    int n;
    vector<Node> nodes;

    void newNode(int &aug, int l, int r) {
        aug = nodes.size();
        nodes.push_back(nodes[0]);
        nodes.back().info = Info(l, r);
    }

    ImplitcitLazySegmentTree(int n) : n(n), nodes(1) {
        int root;
        newNode(root, 0, n);
    }

    void apply(int p, const Tag &t) {
        nodes[p].info.apply(t);
        nodes[p].tag.apply(t);
    }
    void pull(int p) {
        nodes[p].info = nodes[nodes[p].ln].info + nodes[nodes[p].rn].info;
    }
    void push(int p) {
        apply(nodes[p].ln, nodes[p].tag);
        apply(nodes[p].rn, nodes[p].tag);
        nodes[p].tag = Tag();
    }

    void rangeApply(int ql, int qr, const Tag &t) {
        auto dfs = [&](auto self, int p, int l, int r) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) return apply(p, t);
            int m = (l + r) >> 1;
            if (nodes[p].ln == 0) newNode(nodes[p].ln, l, m);
            if (nodes[p].rn == 0) newNode(nodes[p].rn, m, r);
            push(p);
            self(self, nodes[p].ln, l, m);
            self(self, nodes[p].rn, m, r);
            pull(p);
        };
        dfs(dfs, 1, 0, n);
    }

    Info rangeQuery(int ql, int qr) {
        Info res = Info();
        auto dfs = [&](auto self, int p, int l, int r, Tag t) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) {
                Info info = nodes[p].info;
                if (p == 0) info = Info(l, r);
                info.apply(t);
                res = res + info;
                return;
            }
            int m = (l + r) >> 1;
            t.apply(nodes[p].tag);
            self(self, nodes[p].ln, l, m, t);
            self(self, nodes[p].rn, m, r, t);
        };
        dfs(dfs, 1, 0, n, Tag());
        return res;
    }

    template <class F>
    int findFirst(int ql, int qr, F &&pred) {
        Info res = Info();
        auto dfs = [&](auto self, int p, int l, int r, Tag t) -> int {
            if (r <= ql || qr <= l) return -1;
            Info info = nodes[p].info;
            if (p == 0) info = Info(l, r);
            info.apply(t);
            if (ql <= l && r <= qr && !pred(info)) return -1;
            if (l + 1 == r) return l;
            int m = (l + r) >> 1;
            t.apply(nodes[p].tag);
            int get = self(self, nodes[p].ln, l, m, t);
            if (get == -1) get = self(self, nodes[p].rn, m, r, t);
            return get;
        };
        return dfs(dfs, 1, 0, n, Tag());
    }
};

struct Tag {
    int paint = 0;
    void apply(const Tag &t) {
        if (!t.paint) return;
        paint = t.paint;
    }
};

struct Info {
    int len = 0;
    int painted = 0;
    Info() {}
    Info(int l, int r) {
        len = r - l;
    }
    void apply(const Tag &t) {
        if (!t.paint) return;
        painted = len;
    }
    Info operator+(const Info &b) const {
        Info res;
        res.len = len + b.len;
        res.painted = painted + b.painted;
        return res;
    }
};

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

    const int C = 1e9 + 10;
    ImplitcitLazySegmentTree<Info, Tag> seg(C);
    int q;
    cin >> q;
    int ans = 0;
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        l = ans + l;
        r = ans + r;
        l--;
        if (type == 1) {
            ans = seg.rangeQuery(l, r).painted;
            cout << ans << '\n';
        }
        if (type == 2) {
            seg.rangeApply(l, r, {1});
        }
    }
}

• Subtask 1: 100 / 100