Submission #1188642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188642		colonelsven	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	39 ms	884 KiB

apple

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

using ll = long long;

struct Vertex {
    int low, high, sum = 0;
    bool full = false;
    
    Vertex *left_child = nullptr, *right_child = nullptr;

    Vertex(int l, int r) {
        low = l;
        high = r;
    }


    int query(int l, int r) {
        if (low >= l && high <= r) return sum;
        else if (low > r || high < l || low > high) return 0;
        else {
            if (full) {
                return min(r, high) - max(l, low) + 1;
            }
            int mid = (low + high) / 2;
            int left = left_child && l <= mid ? left_child->query(l, r) : 0;
            int right = right_child && r >= mid + 1 ? right_child->query(l, r) : 0;
            return left + right;
        }
    }

    void update(int l, int r) {
        if (full) return;
        if (low >= l && high <= r) {
            full = true;
            sum = high - low + 1;
        }
        else if (low > r || high < l || low > high) return;
        else {
            int mid = (low + high) / 2;
            if (l <= mid) {
                if (!left_child) {
                    left_child = new Vertex(low, mid);
                }
                left_child->update(l, r);
            }
            if (r >= mid + 1) {
                if (!right_child) {
                    right_child = new Vertex(mid + 1, high);
                }
                right_child->update(l, r);
            }
            sum = (left_child ? left_child->sum : 0) + (right_child ? right_child->sum : 0);
        }
    }
};



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int q;
    cin >> q;

    Vertex seg = Vertex(1, 1e9);

    int c = 0;

    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        l += c; r += c;

        if (type == 1) {
            c = seg.query(l, r);
            printf("%i\n", c);
        }
        else {
            seg.update(l, r);
        }
    }
}

• Subtask 1: 100 / 100