Submission #1115668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115668		vanea	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	317 ms	202268 KiB

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) {
    if(tree[curr].l == tree[curr].r) return ;
    if(tree[curr].lazy == 0) return ;
    int mid = (tree[curr].r+tree[curr].l)/2;
    tree[tree[curr].left_child].lazy = 1;
    tree[tree[curr].left_child].sum = (mid-tree[curr].l+1);
    tree[tree[curr].right_child].lazy = 1;
    tree[tree[curr].right_child].sum = (tree[curr].r-mid);
    tree[curr].lazy = 0;
}

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

int query(int l, int r, int curr) {
    if(l <= tree[curr].l && tree[curr].r <= r) return tree[curr].sum;
    if(l > tree[curr].r || r < tree[curr].l) return 0;
    extend_left(curr);
    extend_right(curr);
    propagate(curr);
    return query(l, r, tree[curr].left_child) +
    query(l, r, tree[curr].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;
            c = query(l, r, 0);
            cout << c << '\n';
        }
        else {
            int l, r;
            cin >> l >> r;
            l += c; r += c;
            upd(l, r, 0);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100