제출 #1341523

#제출 시각아이디문제언어결과실행 시간메모리
1341523mwen원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
319 ms198012 KiB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

constexpr ll MAX = 1e9;

struct ST {
    struct Node {
        ll sum, lazy;
        int left, right;
    };
    Node NEW_NODE{0,0,-1,-1};
    
    vector<Node> tree;
    ST() : tree(1, NEW_NODE) {}
    int getLeft(int curr) {
        if(tree[curr].left == -1) {
            tree[curr].left = sz(tree);
            tree.push_back(NEW_NODE);
        }
        return tree[curr].left;
    }
    int getRight(int curr) {
        if(tree[curr].right == -1) {
            tree[curr].right = sz(tree);
            tree.push_back(NEW_NODE);
        }
        return tree[curr].right;
    }
    void push(int curr, ll l, ll r) {
        int L = getLeft(curr);
        int R = getRight(curr);
        ll m = (l+r)/2;
        if(tree[curr].lazy) {
            tree[L].sum = m-l+1;
            tree[L].lazy = 1;
            tree[R].sum = r-(m+1)+1;
            tree[R].lazy = 1;
            tree[curr].lazy = 0;
        }
    }
    void set(int curr, ll l, ll r, ll L, ll R) {
        if(r < L || l > R)
            return;
        if(L <= l && r <= R) {
            tree[curr].sum = r-l+1;
            tree[curr].lazy = 1;
            return;
        }
        push(curr, l, r);

        ll m = (l+r)/2;
        set(getLeft(curr), l, m, L, R);
        set(getRight(curr), m+1, r, L, R);
        tree[curr].sum = tree[getLeft(curr)].sum+tree[getRight(curr)].sum;
    }
    void set(ll L, ll R) {
        set(0, 1, MAX, L, R);
    }
    ll query(int curr, ll l, ll r, ll L, ll R) {
        if(r < L || l > R)
            return 0;
        if(L <= l && r <= R)
            return tree[curr].sum;
        push(curr, l, r);
        ll m = (l+r)/2;
        return  query(getLeft(curr), l, m, L, R) + 
                query(getRight(curr), m+1, r, L, R);
    }
    ll query(ll L, ll R) {
        return query(0, 1, MAX, L, R);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ST tree;
    int q;
    cin >> q;
    ll c = 0;
    while(q-->0) {
        ll d, x, y;
        cin >> d >> x >> y;
        if(d == 1) {
            ll ans = tree.query(x+c, y+c);
            cout << ans << "\n";
            c = ans;
        }
        else {
            tree.set(x+c, y+c);
        }
    }
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...