Submission #729318

#TimeUsernameProblemLanguageResultExecution timeMemory
729318baneMonkey and Apple-trees (IZhO12_apple)C++17
0 / 100
383 ms126052 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxN = 1000000*8;
class SegmentTree{
public:
	int t[maxN];
	int L[maxN];
	int R[maxN];
	int Lz[maxN];
	int cnt = 1;
	
	void propagate(int k, int l, int r){
		if (Lz[k] != 0){
			t[k] = (r - l + 1);
			if (l != r){
				Lz[L[k]] = 1;
				Lz[R[k]] = 1;
			}
			Lz[k] = 0;
		}
	}
	
	void upd(int a, int b, int l = 1, int r = (int)1e9, int k = 1){
		if (!L[k]){
			L[k] = ++cnt;
		}
		if (!R[k]){
			R[k] = ++cnt;
		}
		propagate(k,l,r);
		if (l >= a && r <= b){
			Lz[k] = 1;
			propagate(k,l,r);
			return;
		}
		if (l > b || r < a)return ;
		upd(a,b,l,(l+r)/2,L[k]);
		upd(a,b,(l+r)/2+1,r,R[k]);
		t[k] = t[L[k]] + t[R[k]];
	}
	
	int get(int a, int b, int l = 1, int r = (int)1e9, int k = 1){
		if (!L[k]){
			L[k] = ++cnt;
		}
		if (!R[k]){
			R[k] = ++cnt;
		}
		propagate(k,l,r);
		if (l >= a && r <= b){
			return t[k];
		}
		if (l > b || r < a)return 0;
		int left = 0;
		int right = 0;
		if (L[k])left = get(a,b,l,(l+r)/2,L[k]);
		if (R[k])right = get(a,b,(l+r)/2+1,r,R[k]);
		return right + left;
	}

};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int c = 0;
	SegmentTree Seg;
	for (int i = 0;  i < n; i++){
		int x,y,z;
		cin >> x >> y >> z;
		if (x == 1){
			c = Seg.get(y + c,z + c);
			cout<<c<<'\n';
		}else Seg.upd(c + y, c + z);
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...