Submission #729325

#	Time	Username	Problem	Language	Result	Execution time	Memory
729325		bane	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	152 ms	64272 KiB

apple

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxN = 1000000;
class SegmentTree{
public:
	int t[maxN];
	int L[maxN];
	int R[maxN];
	int Lz[maxN];
	int cnt = 1;
	void extend(int k, int l, int r){
		if (l!=r){
			if (!L[k])L[k]=++cnt;
			if(!R[k])R[k]=++cnt;
		}
	}
	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){
		extend(k,l,r);
		propagate(k,l,r);
		if (a > b)return;
		if (l >= a && r<=b){
			Lz[k]=1;
			t[k] = r - l + 1;
			return;
		}
		if (l > b || r < a)return;
		int md = (l + r) / 2;
		upd(a,b,l,md,L[k]);
		upd(a,b,md+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){
		extend(k,l,r);
		propagate(k,l,r);
		if (a > b)return 0;
		if (l >= a && r <= b)return t[k];
		if (l > b || r < a)return 0;
		int left = 0, right = 0;
		int md = (l+r)/2;
		if (L[k])left = get(a,b,l,md,L[k]);
		if (R[k])right = get(a,b,md+1,r,R[k]);
		return left + right;
	}
	
 
};
signed 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;
}

• Subtask 1: 0 / 100