Submission #941516

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941516	2024-03-09T04:33:31 Z	ifateen	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	335 ms	205884 KB

apple

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 100005;

struct Node {
    int sum;
    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() {
    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	42 ms	100432 KB	Output is correct
2	Correct	27 ms	100444 KB	Output is correct
3	Correct	28 ms	100440 KB	Output is correct
4	Correct	44 ms	100620 KB	Output is correct
5	Correct	46 ms	100564 KB	Output is correct
6	Correct	46 ms	100432 KB	Output is correct
7	Correct	46 ms	100432 KB	Output is correct
8	Correct	149 ms	100908 KB	Output is correct
9	Correct	267 ms	100896 KB	Output is correct
10	Correct	297 ms	100864 KB	Output is correct
11	Correct	271 ms	102776 KB	Output is correct
12	Correct	287 ms	102964 KB	Output is correct
13	Correct	267 ms	102992 KB	Output is correct
14	Correct	272 ms	103216 KB	Output is correct
15	Runtime error	335 ms	205884 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-