제출 #1282950

#제출 시각아이디문제언어결과실행 시간메모리
1282950Jawad_Akbar_JJ원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
33 ms2572 KiB
#include <iostream>

using namespace std;
int N = (1<<30) + 1, n;

struct node{
	node *lft, *rgt;
	bool full = 0, null = 1;

	void set(int l, int r, int st = 1, int en = N){
		if (l >= en or r <= st or full)
			return;
		if (l <= st and r >= en){
			full = 1;
			return;
		}

		int mid = (st + en) / 2;
		if (null)
			lft = new node(), rgt = new node(), null = 0;

		lft->set(l, r, st, mid);
		rgt->set(l, r, mid, en);

		full = lft->full & rgt->full;
	}

	int get(int l, int r, int st = 1, int en = N){
		if (l >= en or r <= st or (full == 0 and null))
			return 0;
		if (full)
			return max(0, min(r, en) - max(l, st));
		int mid = (st + en) / 2;
		return lft->get(l, r, st, mid) + rgt->get(l, r, mid, en);
	}
};

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n;

	node *rt = new node();
	for (int i=1, t, l, r, c = 0;i<=n;i++){
		cin>>t>>l>>r;
		l += c, r += c;
		if (t == 2)
			rt->set(l, r + 1);
		else
			c = rt->get(l, r + 1), cout<<c<<'\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...