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

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.0 / 100.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