제출 #1181582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181582		vincentbucourt1	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	450 ms	230860 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, lazy;
    int nL, nR, idx;
    int iChildL, iChildR;
};
struct Segtree {
    vector<Node> tree;
    Segtree () {
        tree.push_back(Node{0, 0, 1, (1ll << 30), 0, -1, -1});
    }
    void makeChild (int iNode) {
        if (tree[iNode].nL == tree[iNode].nR) return;
        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].lazy, 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), tree[iNode].lazy, nMid+1, tree[iNode].nR, (int)tree.size(), -1, -1});
            tree[iNode].iChildR = (int)tree.size()-1;
        }
    }
    void pushdown (int iNode) {
        makeChild(iNode);
        if (tree[iNode].nL != tree[iNode].nR && tree[iNode].lazy == 1) {
            tree[tree[iNode].iChildL].lazy = 1;
            tree[tree[iNode].iChildR].lazy = 1;
        }
        tree[iNode].val = max(tree[iNode].val, tree[iNode].lazy*(tree[iNode].nR - tree[iNode].nL + 1));
        tree[iNode].lazy = 0;
    }
    int query (int iNode, int qL, int qR) {
        pushdown(iNode);
        if (qL <= tree[iNode].nL && tree[iNode].nR <= qR) {
            return tree[iNode].val*(tree[iNode].nR - tree[iNode].nR + 1);
        }
        else if (tree[iNode].nR < qL || qR < tree[iNode].nL) {
            return 0;
        }
        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) {
        pushdown(iNode);
        if (qL <= tree[iNode].nL && tree[iNode].nR <= qR) {
            tree[iNode].lazy = 1;
            pushdown(iNode);
            return;
        }
        else if (tree[iNode].nR < qL || qR < tree[iNode].nL) {
            return;
        }
        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: 100 / 100