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

apple

#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);
    }
}

Subtask #1

0 / 100.0

#	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	-