Submission #941518

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941518	2024-03-09T04:36:41 Z	ifateen	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	180 ms	101060 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() {
    if (ptr >= 64 * MAXN) exit(24);
    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	19 ms	100444 KB	Output is correct
2	Correct	19 ms	100696 KB	Output is correct
3	Correct	20 ms	100620 KB	Output is correct
4	Correct	31 ms	100648 KB	Output is correct
5	Correct	29 ms	100444 KB	Output is correct
6	Correct	29 ms	100440 KB	Output is correct
7	Correct	29 ms	100444 KB	Output is correct
8	Correct	86 ms	100832 KB	Output is correct
9	Correct	160 ms	100944 KB	Output is correct
10	Correct	180 ms	100992 KB	Output is correct
11	Correct	173 ms	100944 KB	Output is correct
12	Correct	169 ms	100984 KB	Output is correct
13	Correct	148 ms	101060 KB	Output is correct
14	Correct	151 ms	100944 KB	Output is correct
15	Runtime error	161 ms	100944 KB	Execution failed because the return code was nonzero
16	Halted	0 ms	0 KB	-