제출 #1354164

#제출 시각아이디문제언어결과실행 시간메모리
1354164kantaponz원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
156 ms103684 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxNode = 7000000;

struct Node {
    int leftNode = 0;
    int rightNode = 0;
    bool lazy = 0;
    int sum = 0;
} pool[maxNode];

int nodeCnt = 1;

int newNode() {
    return nodeCnt++;
}

void push(int idx, int l, int r) {
    if (!pool[idx].lazy) return;
    if (pool[idx].leftNode == 0) pool[idx].leftNode = newNode();
    if (pool[idx].rightNode == 0) pool[idx].rightNode = newNode();
    pool[idx].lazy = 0;
    int ln = pool[idx].leftNode;
    int rn = pool[idx].rightNode;
    int mid = (l + r) / 2;

    pool[ln].lazy = 1;
    pool[ln].sum = mid - l + 1;

    pool[rn].lazy = 1;
    pool[rn].sum = r - mid;
}

void update(int idx, int l, int r, int a, int b) {
    if (b < l || a > r) return;
    if (pool[idx].lazy == 1) push(idx, l, r);
    if (a <= l && r <= b) {
        pool[idx].lazy = 1;
        pool[idx].sum = r - l + 1;
        return;
    }
    int mid = (l + r) / 2;
    if (pool[idx].leftNode == 0) pool[idx].leftNode = newNode();
    if (pool[idx].rightNode == 0) pool[idx].rightNode = newNode();
    update(pool[idx].leftNode, l, mid, a, b);
    update(pool[idx].rightNode, mid + 1, r, a, b);

    pool[idx].sum = pool[pool[idx].leftNode].sum + pool[pool[idx].rightNode].sum;
}

int query(int idx, int l, int r, int a, int b) {
    if (idx == 0 || b < l || a > r) return 0;
    push(idx, l, r);
    if (a <= l && r <= b) {
        return pool[idx].sum;
    }
    int mid = (l + r) / 2;
    int ln = pool[idx].leftNode;
    int rn = pool[idx].rightNode;
    return query(ln, l, mid, a, b) + query(rn, mid + 1, r, a, b);
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int q;
    cin >> q;
    int c = 0;
    int root = newNode();

    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;

        x += c;
        y += c;

        if (t == 1) {
            int ans = query(root, 1, 1e9, x, y);
            cout << ans << "\n";
            c = ans;
        } else {
            update(root, 1, 1e9, x, y);
        }
    }


}

/*

3
2 5 8
2 7 10
1 1 10

6
*/
#Verdict Execution timeMemoryGrader output
Fetching results...