oj.uz

답안 #941520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941520 2024-03-09T04:42:42 Z ifateen 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 211 ms 133580 KB 
#include <bits/stdc++.h>
using namespace std;

#define mid ((tl + tr) >> 1)

const int MAXN = 1e5 + 3e4;


struct Node {
    int sum = 0;
    bool lazy_set = false;
    int l = 0, r = 0;
} tree[64 * MAXN];

int ptr = 2;
int newchild() {
    return ptr++;
}

void propagate(int tl, int tr, int node) {
    if (tree[node].lazy_set) {
        tree[node].sum = tr - tl + 1;
        if (tl == tr) {
            tree[node].lazy_set = false;
            return;
        }
        if (!tree[node].l) tree[node].l = newchild();
        if (!tree[node].r) tree[node].r = newchild();
        tree[tree[node].l].lazy_set = true;
        tree[tree[node].r].lazy_set = true;
    }
    tree[node].lazy_set = false;
}

void update(int tl, int tr, int node, int l, int r) {
    propagate(tl, tr, node);
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
        tree[node].lazy_set = true;
        propagate(tl, tr, node);
        return;
    }
    if (!tree[node].l) tree[node].l = newchild();
    if (!tree[node].r) tree[node].r = newchild();
    update(tl, mid, tree[node].l, l, r);
    update(mid + 1, tr, tree[node].r, l, r);
    tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
}

int query(int tl, int tr, int node, int l, int r) {
    propagate(tl, tr, node);
    if (tl > r || tr < l) return 0;
    if (tl >= l && tr <= r) {
        return tree[node].sum;
    }
    int ret = 0;
    if (tree[node].l) ret += query(tl, mid, tree[node].l, l, r);
    if (tree[node].r) ret += query(mid + 1, tr, tree[node].r, l, r);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for (auto& i : tree) i.l = 0, i.r = 0, i.sum = 0, i.lazy_set = false;
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        l += c, r += c;
        if (t == 1) cout << (c = query(1, 1'000'000'000, 1, l, r)) << '\n';
        else update(1, 1'000'000'000, 1, l, r);
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 130648 KB Output is correct
2 Correct 26 ms 130524 KB Output is correct
3 Correct 25 ms 130652 KB Output is correct
4 Correct 33 ms 130516 KB Output is correct
5 Correct 33 ms 130644 KB Output is correct
6 Correct 34 ms 130736 KB Output is correct
7 Correct 33 ms 130568 KB Output is correct
8 Correct 84 ms 130644 KB Output is correct
9 Correct 159 ms 130896 KB Output is correct
10 Correct 168 ms 131044 KB Output is correct
11 Correct 178 ms 130888 KB Output is correct
12 Correct 164 ms 131036 KB Output is correct
13 Correct 156 ms 131156 KB Output is correct
14 Correct 157 ms 131160 KB Output is correct
15 Correct 203 ms 131264 KB Output is correct
16 Correct 210 ms 133456 KB Output is correct
17 Correct 160 ms 133360 KB Output is correct
18 Correct 163 ms 133208 KB Output is correct
19 Correct 205 ms 133200 KB Output is correct
20 Correct 211 ms 133580 KB Output is correct