Submission #872548

#	Time	Username	Problem	Language	Result	Execution time	Memory
872548		andrei_c1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	71 ms	3076 KiB

apple

#include <bits/stdc++.h>

using namespace std;

struct chtholly {
    struct node_t {
        int l, r;
        mutable int v;
        node_t() {}
        node_t(int l, int r, int v): l(l), r(r), v(v) {}
        bool operator < (const node_t &oth) const {
            return l < oth.l;
        }
    };
    int n;
    set<node_t> tree;
    chtholly() {}
    chtholly(int n): n(n) {
        tree.emplace(0, n - 1, 0);
    }
    set<node_t>::iterator split(int x) {
        auto it = tree.lower_bound(node_t(x, -1, 0));
        if(it != tree.end() && it->l == x) {
            return it;
        }
        it--;
        if(it->r < x) {
            return tree.end();
        }
        int l = it->l, r = it->r, v = it->v;
        tree.erase(it);
        tree.emplace(l, x - 1, v);
        return tree.emplace(x, r, v).first;
    }
    void flatten(int l, int r, int v) {
        auto R = split(r + 1), L = split(l);
        tree.erase(L, R);
        tree.emplace(l, r, v);
    }
    int query(int l, int r) {
        auto R = split(r + 1), L = split(l);
        int res = 0;
        while(L != R) {
            res += L->v * (L->r - L->l + 1);
            L++;
        }
        return res;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    chtholly ds(1e9);
    for(int i = 0, c = 0; i < n; i++) {
        int t, l, r;
        cin >> t >> l >> r;

        l += c - 1;
        r += c - 1;

        if(t == 1) {
            c = ds.query(l, r);
            cout << c << '\n';
        } else {
            ds.flatten(l, r, 1);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100