Submission #1181574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181574		vincentbucourt1	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	0 ms	328 KiB

apple

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long

int N;

struct Node {
    int val, nL, nR, idx, iChildL, iChildR;
};
struct Segtree {
    vector<Node> tree;
    Segtree () {
        tree.push_back(Node{0, 0, (1ll << 30)-1, 0, -1, -1});
    }
    void makeChild (int iNode) {
        if (tree[iNode].iChildL == -1 || tree[iNode].iChildR == -1) {
            int nMid = (tree[iNode].nL + tree[iNode].nR) / 2;
            tree.push_back(Node{(tree[iNode].val > 0 ? tree[iNode].val/2 : 0), tree[iNode].nL, nMid, (int)tree.size(), -1, -1});
            tree[iNode].iChildL = (int)tree.size()-1;
            tree.push_back(Node{(tree[iNode].val > 0 ? tree[iNode].val/2 : 0), nMid+1, tree[iNode].nR, (int)tree.size(), -1, -1});
            tree[iNode].iChildR = (int)tree.size()-1;
        }
    }
    int query (int iNode, int qL, int qR) {
        if (qL <= tree[iNode].nL && tree[iNode].nR <= qR) {
            return tree[iNode].val;
        }
        else if (tree[iNode].nR < qL || qR < tree[iNode].nL) {
            return 0;
        }
        makeChild(iNode);
        return query(tree[iNode].iChildL, qL, qR) + query(tree[iNode].iChildR, qL, qR);
    }
    int query (int l, int r) {
        return query(0, l, r);
    }
    void update (int iNode, int qL, int qR) {
        if (qL <= tree[iNode].nL && tree[iNode].nR <= qR) {
            tree[iNode].val = (tree[iNode].nR - tree[iNode].nL + 1);
            return;
        }
        else if (tree[iNode].nR < qL || qR < tree[iNode].nL) {
            return;
        }
        makeChild(iNode);
        update(tree[iNode].iChildL, qL, qR);
        update(tree[iNode].iChildR, qL, qR);
        tree[iNode].val = tree[tree[iNode].iChildL].val + tree[tree[iNode].iChildR].val;
    }
    void update (int l, int r) {
        return update(0, l, r);
    }
};

signed main() {
    fastIO();
    cin >> N;
    Segtree interQ;
    int offset = 0;
    for (int i = 0; i < N; i++) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            int res = interQ.query(l+offset, r+offset);
            offset = res;
            cout << res << "\n";
        }
        else {
            assert(type == 2);
            interQ.update(l+offset, r+offset);
        }
    }
}

• Subtask 1: 0 / 100