Submission #1041276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041276		Thunnus	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	381 ms	207864 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;
    }

    ~Vertex(){
        delete lc;
        delete rc;
    }
 
    inline void extend(){
        if(!lc && tl != tr){
            int mid = (tl + tr) / 2;
            lc = new Vertex(tl, mid);
            rc = new Vertex(mid + 1, tr);
        }
    }
 
    inline void propagate(){
		extend();
        if(!lazy_set || !lc) 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;
        }
        propagate();
        lc->update(l, r, val);
        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;
        propagate();
        return lc->query(l, r) + rc->query(l, r);
    }
};
 
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: 100 / 100