Submission #1188606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188606		colonelsven	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	393 ms	327680 KiB

apple

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

using ll = long long;

struct Vertex {
    int low, high, sum = 0, lazy = 0;
    
    Vertex *left_child = nullptr, *right_child = nullptr;

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

    void propagate() {
        sum = max(sum, (lazy * (high - low + 1)));
        if (low != high && lazy > 0) {
            int mid = (low + high) / 2;
            if (!left_child) {
                left_child = new Vertex(low, mid);
            }
            if (!right_child) {
                right_child = new Vertex(mid + 1, high);
            }
            left_child->lazy = 1;
            right_child->lazy = 1;
        }
        lazy = 0;
    }

    int query(int l, int r) {
        propagate();
        if (low >= l && high <= r) return sum;
        else if (low > r || high < l || low > high) return 0;
        else {
            int left = left_child ? left_child->query(l, r) : 0;
            int right = right_child ? right_child->query(l, r) : 0;
            return left + right;
        }
    }

    void update(int l, int r) {
        propagate();
        if (low >= l && high <= r) {
            lazy = 1;
            propagate();
        }
        else if (low > r || high < l || low > high) return;
        else {
            int mid = (low + high) / 2;
            if (!left_child) {
                left_child = new Vertex(low, mid);
            }
            left_child->update(l, r);

            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: 0 / 100