Submission #1115608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1115608	2024-11-20T16:59:38 Z	vanea	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	3 ms	592 KB

apple

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

struct Node {
    int sum = 0, lazy = 0;
    int l, r;
    int left_child = -1, right_child = -1;
    Node(int lb, int rb) {
        l = lb;
        r = rb;
    }
};

int n, cnt = 0;

vector<Node> tree;

void extend_left(int curr) {
    if(tree[curr].left_child == -1 && tree[curr].l != tree[curr].r) {
        int mid = (tree[curr].l+tree[curr].r)/2;
        tree[curr].left_child = ++cnt;
        tree.push_back(Node(tree[curr].l, mid));
    }
}

void extend_right(int curr) {
    if(tree[curr].right_child == -1 && tree[curr].l != tree[curr].r) {
        int mid = (tree[curr].l+tree[curr].r)/2;
        tree[curr].right_child = ++cnt;
        tree.push_back(Node(mid+1, tree[curr].r));
    }
}

void propagate(int curr) {
    Node& x = tree[curr];
    if(x.l == x.r) return ;
    if(x.lazy == 0) return ;
    int mid = (x.r+x.l)/2;
    tree[x.left_child].lazy = 1;
    tree[x.left_child].sum = (mid-x.l+1);
    tree[x.right_child].lazy = 1;
    tree[x.right_child].sum = (x.r-mid);
    x.lazy = 0;
}

void upd(int l, int r, int curr) {
    extend_left(curr);
    extend_right(curr);
    propagate(curr);
    Node& x = tree[curr];
    if(l <= x.l && x.r <= r) {
        x.lazy = 1;
        x.sum = (x.r-x.l+1);
        return ;
    }
    if(l > x.r || r < x.l) return ;
    upd(l, r, x.left_child);
    upd(l, r, x.right_child);
    x.sum = tree[x.left_child].sum+tree[x.right_child].sum;
}

int query(int l, int r, int curr) {
    extend_left(curr);
    extend_right(curr);
    propagate(curr);
    Node& x = tree[curr];
    if(l <= x.l && x.r <= r) return x.sum;
    if(l > x.r || r < x.l) return 0;
    return query(l, r, x.left_child) +
    query(l, r, x.right_child);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q;
    cin >> q;
    tree.reserve(2 * q * __lg(n));
    tree.push_back(Node(0, 1e9+1));
    int c = 0;
    while(q--) {
        int flag;
        cin >> flag;
        if(flag == 1) {
            int l, r;
            cin >> l >> r;
            l += c; r += c;
            int k = query(l, r, 0);
            c += k;
            cout << k << '\n';
        }
        else {
            int l, r;
            cin >> l >> r;
            l += c; r += c;
            upd(l, r, 0);
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	3 ms	592 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-