Submission #729330

#	Time	Username	Problem	Language	Result	Execution time	Memory
729330		bane	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	586 ms	132860 KiB

apple

#include<bits/stdc++.h>
using namespace std;
#define ll long long
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;
	Seg.init(1e9);
	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: 100 / 100