Submission #941519

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941519	2024-03-09T04:41:16 Z	ifateen	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	31 ms	130652 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;
    }
    int sm = 0;
    if (l > mid) {
        if (!tree[node].r) tree[node].r = newchild();
        update(mid + 1, tr, tree[node].r, l, r);
        sm += tree[tree[node].r].sum;
        if (tree[node].l) sm += tree[tree[node].l].sum;
    } else if (r <= mid) {
        if (!tree[node].l) tree[node].l = newchild();
        update(tl, mid, tree[node].l, l, r);
        sm += tree[tree[node].l].sum;
        if (tree[node].r) sm += tree[tree[node].r].sum;
    } else {
        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);
        sm += tree[tree[node].l].sum;
        sm += tree[tree[node].r].sum;
    }
    tree[node].sum = sm;
}

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	31 ms	130652 KB	Output is correct
2	Correct	24 ms	130652 KB	Output is correct
3	Incorrect	25 ms	130652 KB	Output isn't correct
4	Halted	0 ms	0 KB	-