답안 #951374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
951374 2024-03-21T18:03:08 Z sheldon 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
170 ms 128340 KB
#include <bits/stdc++.h>

using namespace std;


struct Node {
    int left = -1, right = -1, ans = 0, lazy = 0;
    int sz;


    void push (Node &l, Node &r) {
        if (lazy) {
            l.ans = l.sz;
            r.ans = r.sz;
            l.lazy = 1;
            r.lazy = 1;
            lazy = 0;
        }
    }

    void get (Node &l, Node &r) {
        ans = l.ans + r.ans;
    }
};
const int nax = 100000;
Node tree[nax * 64];
int idx = 2;

void create (int node, int l, int r) {
    if (tree[node].left == -1) {
        tree[node].left = idx;
        tree[idx].sz  = (l + r) / 2 - l + 1;
        ++idx;
    }
    // maybe l > r ???
    if (tree[node].right == -1) {
        tree[node].right = idx;
        tree[idx].sz = r - ((l + r) / 2 + 1) + 1; 
        ++idx;
    }
}


void update (int node, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) {
        return;
    }


    if (ql <= l && r <= qr) {
        tree[node].ans = r - l + 1;
        tree[node].lazy = 1;
        return;
    }

    int mid = (l + r) / 2;
    create (node, l, r);
    tree[node].push (tree[tree[node].left], tree[tree[node].right]);
    update (tree[node].left, l, mid, ql, qr);
    update (tree[node].right, mid + 1, r, ql, qr);
    tree[node].get (tree[tree[node].left], tree[tree[node].right]);
}

int query (int node, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) {
        return 0;
    }

    if (ql <= l && r <= qr) {
        return tree[node].ans;
    }

    int mid = (l + r) / 2;
    create (node, l, r);
    tree[node].push (tree[tree[node].left], tree[tree[node].right]);
    return query (tree[node].left, l, mid, ql, qr) + query (tree[node].right, mid + 1, r, ql, qr);


}

void solve() {
    int q;
    cin >> q;
    int c = 0;

    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
        
        if (type == 1) {
            c = query (1, 1, 1e9 + 5, l + c, r + c);
            cout << c << '\n';
        } else {
            update (1, 1, 1e9 + 5, l + c, r + c);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}
# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 125520 KB Output is correct
2 Correct 23 ms 125528 KB Output is correct
3 Correct 23 ms 125528 KB Output is correct
4 Correct 28 ms 125724 KB Output is correct
5 Correct 30 ms 125700 KB Output is correct
6 Correct 31 ms 125996 KB Output is correct
7 Correct 30 ms 125780 KB Output is correct
8 Correct 73 ms 126548 KB Output is correct
9 Correct 127 ms 127772 KB Output is correct
10 Correct 138 ms 127692 KB Output is correct
11 Correct 133 ms 127824 KB Output is correct
12 Correct 135 ms 127824 KB Output is correct
13 Correct 127 ms 128080 KB Output is correct
14 Correct 133 ms 128308 KB Output is correct
15 Correct 170 ms 128084 KB Output is correct
16 Correct 162 ms 128300 KB Output is correct
17 Correct 128 ms 128080 KB Output is correct
18 Correct 125 ms 128084 KB Output is correct
19 Correct 164 ms 128268 KB Output is correct
20 Correct 164 ms 128340 KB Output is correct