Submission #729324

#	Time	Username	Problem	Language	Result	Execution time	Memory
729324		bane	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	726 ms	262144 KiB

apple

#include<bits/stdc++.h>
using namespace std;
#define int long long
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;
		return	get(a,b,l,(l+r)/2,L[k]) + get(a,b,(l+r)/2+1,r,R[k]);
	}
 
};
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