Submission #941517

# Submission time Handle Problem Language Result Execution time Memory
941517 2024-03-09T04:35:40 Z ifateen Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
244 ms 204076 KB
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 100005;

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);
    }
}
# Verdict Execution time Memory Grader output
1 Correct 44 ms 100436 KB Output is correct
2 Correct 19 ms 100444 KB Output is correct
3 Correct 21 ms 100616 KB Output is correct
4 Correct 30 ms 100436 KB Output is correct
5 Correct 29 ms 100444 KB Output is correct
6 Correct 31 ms 100660 KB Output is correct
7 Correct 28 ms 100436 KB Output is correct
8 Correct 79 ms 100700 KB Output is correct
9 Correct 150 ms 100948 KB Output is correct
10 Correct 158 ms 100944 KB Output is correct
11 Correct 163 ms 100948 KB Output is correct
12 Correct 172 ms 100800 KB Output is correct
13 Correct 144 ms 100948 KB Output is correct
14 Correct 157 ms 101156 KB Output is correct
15 Runtime error 244 ms 204076 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -