제출 #1187820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187820		pacman	원숭이와 사과 나무 (IZhO12_apple)	C++20	100 / 100	176 ms	69112 KiB

apple

#include <bits/stdc++.h>
//#define int int64_t

using namespace std;

const int maxn = 1e9;

int Q, C;


struct segment_tree{
    struct node{
        int sum = 0 ,lazy = 0, left = -1 , right = -1;
    };
    vector<node> seg;
    segment_tree(){
        seg.reserve(2 * 100000 * 30);
        seg.push_back(node());
        seg.push_back(node());
    }
    int sz = 1;

    void shfit(int v ,int L, int R){
        if(seg[v].left == -1){
            seg[v].left = ++sz;
            seg.push_back(node());
        }
        if(seg[v].right == -1){
            seg[v].right = ++sz;
            seg.push_back(node());
        }
        int mid = (R + L) / 2;
        if(seg[v].lazy == 1){
            seg[seg[v].left].lazy = 1;
            seg[seg[v].left].sum = (mid - L + 1);
            seg[seg[v].right].lazy = 1;
            seg[seg[v].right].sum = (R - mid);
            seg[v].lazy = 0;
        }
    }


    void update(int v ,int L, int R ,int l, int r){
        if(l > R or L > r or l > r or L > R){
            return;
        }
        if(l <= L and R <= r){
            seg[v].lazy = 1;
            seg[v].sum = (R - L + 1);
            return;
        }
        shfit(v ,L, R);
        int mid = (R + L) / 2;
        update(seg[v].left, L, mid ,l ,r);
        update(seg[v].right, mid + 1, R ,l, r);
        seg[v].sum = (seg[seg[v].left].sum + seg[seg[v].right].sum);
    }

    int get(int v, int L, int R, int l, int r){
        if(L > r or l > R or l > r or L > R){
            return 0;
        }
        if(l <= L and R <= r){
            return seg[v].sum;
        }
        shfit(v ,L ,R);
        int mid = (R + L) / 2;
        return (get(seg[v].left, L, mid , l, r) + get(seg[v].right, mid + 1, R , l, r));
    }
}seg;


void in(){
    cin >> Q;
}


void out(){
    while(Q--){
        int type, l ,r;
        cin >> type >> l >> r;
        l--, r--;
        if(type == 1){
            C = seg.get(1 ,0 , maxn - 1, l + C, r + C);
            cout << C << "\n";
        }
        else{
            seg.update(1 ,0, maxn - 1, l + C , r + C);
        }
    }
}


int32_t main(){

    ios::sync_with_stdio(0) ,cout.tie(0) ,cin.tie(0);

    in();
    out();
    
    return 0;
}

• Subtask 1: 100 / 100