Submission #941520

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941520	2024-03-09T04:42:42 Z	ifateen	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	211 ms	133580 KB

apple

#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

#	Verdict	Execution time	Memory	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