제출 #1041267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041267		Thunnus	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	0 ms	344 KiB

apple

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

struct Vertex{
    int sum = 0, lazy_set = 0, tl, tr;
    Vertex *lc = nullptr, *rc = nullptr;
    Vertex(int lb, int rb){
        tl = lb, tr = rb;
    }

    inline void extend(){
        if(!lc){
            int mid = (tl + tr) / 2;
            lc = new Vertex(tl, mid);
            rc = new Vertex(mid + 1, tr);
        }
    }

    inline void propagate(){
		extend();
        if(!lazy_set) return;
        int mid = (tl + tr) / 2;
        lc->lazy_set = rc->lazy_set = lazy_set;
        lc->sum = (mid - tl + 1) * lazy_set;
        rc->sum = (tr - mid) * lazy_set;
        lazy_set = 0;
    }

    void update(int l, int r, int val){
        if(r < tl || l > tr) return;
        if(r >= tr && l <= tl){
            sum = (tr - tl + 1) * val;
            lazy_set = val;
            return;
        }
        int mid = (tl + tr) / 2;
        propagate();
        if(l <= mid)
            lc->update(l, r, val);
        if(r > mid)
            rc->update(l, r, val);
        sum = lc->sum + rc->sum;
    }

    int query(int l, int r){
        if(r < tl || l > tr) return 0ll;
        if(r >= tr && l <= tl) return sum;
        int mid = (tl + tr) / 2, sm1 = 0, sm2 = 0;
        propagate();
        if(l <= mid)
            sm1 = lc->query(l, r);
        if(r > mid)
            sm2 = lc->query(l, r);
        return sm1 + sm2;
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    Vertex st(1, 1e9);
    int m, type, l, r, c = 0;
    cin >> m;
    while(m--){
        cin >> type >> l >> r;
        if(type == 1){
            c = st.query(l + c, r + c);
            cout << c << "\n";
        }
        else{
            st.update(l + c, r + c, 1);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100