제출 #1319857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319857		24ta_tdanh	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	247 ms	137440 KiB

apple

#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ce cout << endl
#define ALL(A) A.begin(), A.end()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using str = string;
using ull = unsigned long long;
using ld = long double; 
const int INF = 1e9;
const int N = 1e4;
const int LOGN = 14;
const int C = 2000;
const int heavy = 500;
const int MOD = 1e9 + 7;
const int Q = 50000;
int dx[] = {0, 1, 0, -1}; // east, south, west, north
int dy[] = {1, 0, -1, 0};

// T_Danh - Tri An High School
struct SegmentTree{
private:
    struct NODE{
        int freq = 0; 
        int lazy = 0;
        NODE *left  = nullptr;
        NODE *right  = nullptr;
    };    
    NODE *root = new NODE;
    const int n;
    int comb(int a, int b){
        return a  + b;
    }
    void apply(NODE *cur , int len, int val){
        if(val == 1){
            cur->lazy = val;
            cur->freq = len * val;
        }
    }
    void down(NODE *cur , int l , int r){
        if( cur->left == nullptr) cur->left = new NODE;
        if( cur->right == nullptr) cur->right = new NODE;
        int mid = l + r >> 1;
        apply(cur->left , mid - l + 1 , cur->lazy);
        apply(cur->right , r - mid , cur->lazy);
        cur->lazy=  0;
    }
    void upd_set(NODE *cur , int l ,int r , int u , int v ,int val){
        if(u > r || v < l) return;
        if(u <= l && r <= v){
            apply(cur, r - l  + 1 , val);
            return;
        }
        down(cur , l , r);
        int mid = l + r >> 1;
        upd_set(cur->left , l , mid , u , v ,val);
        upd_set(cur->right , mid + 1 ,r , u , v , val);
        cur->freq = comb(cur->left->freq , cur->right->freq);
    }
    int get(NODE *cur ,int l , int r ,int u , int v){
        if(v < l || u > r ) return 0;
        if(u <= l && r <= v) return cur->freq;
        down(cur , l , r);
        int mid = l + r >> 1;
        return comb(get(cur->left , l ,mid , u , v) , get(cur->right , mid + 1 , r , u , v));
    }
public:
	SegmentTree(int n) : n(n) {}        
    void upd(int u ,  int v , int val){
        upd_set(root , 0 , n - 1 , u , v ,val);
    }
    int query(int l ,int r){
        return get(root , 0 , n - 1 , l , r);
    }
};



void solve(){
    int q;
    cin >> q;
    const int N = 1e9;
    int c =0 ;
    SegmentTree st(N + 1);
    FOR(i,0,q -1){
        int t, l , r;
        cin >> t >> l >> r;
        if(t == 1){
            c = st.query(l + c , r + c);
            cout << c <<endl;
        }
        else{
            st.upd(l + c, r + c , 1);
        }
    }




}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int t = 1;
    while (t--) solve();
    return 0;
}

• Subtask 1: 100 / 100