제출 #729329

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

apple

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 1000000;
struct segtree{
    vector<int> tree, lazy, L, R;
    int size = 0;
    int create(){
        tree.push_back(0);
        lazy.push_back(0);
        L.push_back(0);
        R.push_back(0);
        return tree.size() - 1;
    }
    void init(int n){
        create();
        size = n;
        create();
    }
    void propagate(int x, int lx, int rx){
        if(lazy[x] == 0 || lx == rx) return;
        int mx = (lx + rx) / 2;
        if(!L[x]) L[x] = create();
        tree[L[x]] = mx - lx + 1;
        lazy[L[x]] = 1;
        if(!R[x]) R[x] = create();
        tree[R[x]] = rx - mx;
        lazy[R[x]] = 1;
        lazy[x] = 0;
    }
    void update(int l, int r, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(r < lx || rx < l) return;
        if(l <= lx && rx <= r){
            tree[x] = rx - lx + 1;
            lazy[x] = 1;
            return;
        } 
        int mx = (lx + rx) / 2;
        if(!L[x]) L[x] = create();
        update(l, r, L[x], lx, mx);
        if(!R[x]) R[x] = create();
        update(l, r, R[x], mx + 1, rx);
        tree[x] = tree[L[x]] + tree[R[x]];
    }
    void update(int l, int r){
        update(l, r, 1, 1, size);
    }
    ll query(int l, int r, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(r < lx || rx < l) return 0;
        if(l <= lx && rx <= r) return tree[x];
        int mx = (lx + rx) / 2;
        ll left = 0, right = 0;
        if(L[x]) left = query(l, r, L[x], lx, mx);
        if(R[x]) right = query(l, r, R[x], mx + 1, rx);
        return left + right;
    }
    ll query(int l, int r){
        return query(l, r, 1, 1, size);
    }
};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int c = 0;
	segtree Seg;
	for (int i = 0;  i < n; i++){
		int x,y,z;
		cin >> x >> y >> z;
		if (x == 1){
			c = Seg.query(y + c,z + c);
			cout<<c<<'\n';
		}else Seg.update(c + y, c + z);
	}
	return 0;
}

• Subtask 1: 0 / 100