Submission #872548

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
872548	2023-11-13T10:52:07 Z	andrei_c1	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	71 ms	3076 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	7 ms	604 KB	Output is correct
5	Correct	7 ms	604 KB	Output is correct
6	Correct	7 ms	604 KB	Output is correct
7	Correct	7 ms	604 KB	Output is correct
8	Correct	33 ms	1364 KB	Output is correct
9	Correct	67 ms	2384 KB	Output is correct
10	Correct	66 ms	2400 KB	Output is correct
11	Correct	66 ms	2388 KB	Output is correct
12	Correct	71 ms	2652 KB	Output is correct
13	Correct	64 ms	2952 KB	Output is correct
14	Correct	64 ms	2896 KB	Output is correct
15	Correct	69 ms	2900 KB	Output is correct
16	Correct	68 ms	2900 KB	Output is correct
17	Correct	68 ms	2900 KB	Output is correct
18	Correct	64 ms	2900 KB	Output is correct
19	Correct	69 ms	3076 KB	Output is correct
20	Correct	70 ms	2872 KB	Output is correct