제출 #918424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918424		asdasdqwer	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	285 ms	135332 KiB

apple

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

struct Node {
    int sum = 0;
    int lIdx = -1;
    int rIdx = -1;
    int upd = 0;
};

struct Segtree {
    int n = 1<<30;
    vector<Node> seg;

    Segtree(int sjkd) {
        Node n1;
        seg = {n1};
    }

    void gen(int idx) {
        Node n1;
        seg.push_back(n1);
        seg.push_back(n1);
        seg[idx].lIdx = seg.size() - 2;
        seg[idx].rIdx = seg.size() - 1;
    }

    void pushdown(int idx, int l, int r) {
        if (seg[idx].upd == 0) {
            return;
        }

        int len = (r-l)/2;

        seg[seg[idx].lIdx].sum = seg[seg[idx].rIdx].sum = len;
        seg[seg[idx].lIdx].upd = seg[seg[idx].rIdx].upd = seg[idx].upd;

        seg[idx].upd = 0;
    }

    int get(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return 0;
        if (rx - lx == 1) {
            return seg[x].sum;
        }

        if (seg[x].lIdx == -1) {
            gen(x);
            seg[seg[x].lIdx].sum = seg[seg[x].rIdx].sum = seg[x].sum / 2;
        }

        pushdown(x, lx, rx);

        if (lx >= l && rx <= r) {
            return seg[x].sum;
        }

        int m=(lx+rx)/2;

        return get(l, r, seg[x].lIdx, lx, m) + get(l, r, seg[x].rIdx, m, rx);
    }

    int get(int l, int r) {
        return get(l, r, 0, 0, n);
    }

    void set(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return;
        if (rx - lx == 1) {
            seg[x].sum = 1;
            return;
        }

        if (seg[x].lIdx == -1) {
            gen(x);
            seg[seg[x].lIdx].sum = seg[seg[x].rIdx].sum = seg[x].sum / 2;
        }

        pushdown(x, lx, rx);

        if (lx >= l && rx <= r) {
            seg[x].sum = rx-lx;
            seg[x].upd = 1;
            return;
        }

        int m=(lx+rx)/2;
        set(l, r, seg[x].lIdx, lx, m);
        set(l, r, seg[x].rIdx, m, rx);

        seg[x].sum = seg[seg[x].lIdx].sum + seg[seg[x].rIdx].sum;
    }

    void set(int l, int r) {
        set(l, r, 0, 0, n);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m;cin>>m;
    int c=0;

    Segtree sg(45);

    while (m--) {
        int code;cin>>code;
        int x,y;cin>>x>>y;
        if (code == 1) {
            x += c;y += c;
            int ans = sg.get(x, y+1);
            cout<<ans<<"\n";
            c = ans;
        }

        else {
            x += c;y += c;
            sg.set(x, y+1);
        }
    }
}

• Subtask 1: 100 / 100