제출 #1254427

#제출 시각아이디문제언어결과실행 시간메모리
1254427Thunnus원숭이와 사과 나무 (IZhO12_apple)C++17
100 / 100
300 ms205720 KiB
#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 fi first
#define se second
#define pii pair<int, int>
#define sz(x) (int)(x).size()

struct Node{
    Node *lc = nullptr, *rc = nullptr;
    int sm = 0, lazy = 0, tl, tr;
    Node(int l, int r) : tl(l), tr(r) {}

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

    inline void propagate(){
		extend();
        if(!lazy || tl == tr) return;
        int mid = (tl + tr)  / 2;
        lc->lazy = lazy;
        lc->sm = lazy * (mid - tl + 1);
        rc->lazy = lazy;
        rc->sm = lazy * (tr - mid);
        lazy = 0;
        return;
    }
    
    inline void update(int ul, int ur, int val){
        if(ul > tr || tl > ur) return;
        if(ul <= tl && tr <= ur){
            lazy = val;
            sm = val * (tr - tl + 1);
            return;
        }
        propagate();
        lc->update(ul, ur, val);
        rc->update(ul, ur, val);
        sm = lc->sm + rc->sm;
        return;
    }

    inline int query(int ql, int qr){
        if(ql > tr || tl > qr) return 0ll;
        if(ql <= tl && tr <= qr) return sm;
        propagate();
        return lc->query(ql, qr) + rc->query(ql, qr);
    }
};

inline void solve(){
    Node 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;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...