제출 #1188608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188608		colonelsven	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	399 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 (l <= mid) {
                if (!left_child) {
                    left_child = new Vertex(low, mid);
                }
                left_child->update(l, r);
            }
            else {
                if (left_child) {
                    left_child->propagate();
                }
            }
            if (r >= mid + 1) {
                if (!right_child) {
                    right_child = new Vertex(mid + 1, high);
                }
                right_child->update(l, r);
            }
            else {
                if (right_child) {
                    right_child->propagate();
                }
            }
            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