Submission #729330

# Submission time Handle Problem Language Result Execution time Memory
729330 2023-04-23T19:42:38 Z bane Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
586 ms 132860 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 19 ms 3304 KB Output is correct
5 Correct 21 ms 3756 KB Output is correct
6 Correct 20 ms 3672 KB Output is correct
7 Correct 20 ms 3804 KB Output is correct
8 Correct 180 ms 26184 KB Output is correct
9 Correct 387 ms 44260 KB Output is correct
10 Correct 372 ms 49584 KB Output is correct
11 Correct 392 ms 53636 KB Output is correct
12 Correct 379 ms 55512 KB Output is correct
13 Correct 368 ms 83208 KB Output is correct
14 Correct 374 ms 83196 KB Output is correct
15 Correct 586 ms 126852 KB Output is correct
16 Correct 551 ms 129856 KB Output is correct
17 Correct 399 ms 85104 KB Output is correct
18 Correct 391 ms 85264 KB Output is correct
19 Correct 556 ms 132860 KB Output is correct
20 Correct 583 ms 132824 KB Output is correct