답안 #870653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
870653 2023-11-08T17:31:54 Z Irate 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
304 ms 119968 KB
#include<bits/stdc++.h>
using namespace std;
const int mxN = 1e7;
struct SegmentTree{
	vector<int>sTree, L, R;
	vector<bool>lazy;
	int nxt = 1;
	SegmentTree(){
		sTree.resize(mxN);
		L.resize(mxN);
		R.resize(mxN);
		lazy.resize(mxN);
	}
	void Propagate(int node, int l, int r){
		if(!lazy[node])return;
		sTree[node] = r - l + 1;
		if(l != r){
			if(!L[node])L[node] = ++nxt;
			if(!R[node])R[node] = ++nxt;
			lazy[L[node]] = 1;
			lazy[R[node]] = 1;
		}
		lazy[node] = 0;
	}
	void Update(int node, int l, int r, int ql, int qr){
		Propagate(node, l, r);
		if(ql <= l && r <= qr){
			lazy[node] = 1;
			Propagate(node, l, r);
			return;
		}
		if(ql > r || l > qr)return;
		int mid = (l + r) >> 1;
		if(!L[node])L[node] = ++nxt;
		if(!R[node])R[node] = ++nxt;
		Update(L[node], l, mid, ql, qr);
		Update(R[node], mid + 1, r, ql, qr);
		sTree[node] = sTree[L[node]] + sTree[R[node]]; 
	}
	int Query(int node, int l, int r, int ql, int qr){
		Propagate(node, l, r);
		if(ql <= l && r <= qr)return sTree[node];
		if(ql > r || l > qr)return 0;
		int mid = (l + r) >> 1;
		int lc = 0, rc = 0;
		if(L[node])lc = Query(L[node], l, mid, ql, qr);
		if(R[node])rc = Query(R[node], mid + 1, r, ql, qr);
		return lc + rc;
	}
};
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int q, C = 0;
	cin >> q;
	SegmentTree tree;
	while(q--){
		int d, x, y;
		cin >> d >> x >> y;
		x += C;
		y += C;
		if(d == 1){
			int sum = tree.Query(1, 1, 1e9, x, y);
			cout << sum << "\n";
			C = sum;
		}
		else{
			tree.Update(1, 1, 1e9, x, y);	
		}
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 118868 KB Output is correct
2 Correct 16 ms 118872 KB Output is correct
3 Correct 17 ms 118996 KB Output is correct
4 Correct 26 ms 118892 KB Output is correct
5 Correct 27 ms 119128 KB Output is correct
6 Correct 28 ms 119124 KB Output is correct
7 Correct 27 ms 119128 KB Output is correct
8 Correct 104 ms 119132 KB Output is correct
9 Correct 202 ms 119468 KB Output is correct
10 Correct 200 ms 119376 KB Output is correct
11 Correct 205 ms 119616 KB Output is correct
12 Correct 213 ms 119332 KB Output is correct
13 Correct 202 ms 119476 KB Output is correct
14 Correct 191 ms 119968 KB Output is correct
15 Correct 272 ms 119544 KB Output is correct
16 Correct 279 ms 119404 KB Output is correct
17 Correct 192 ms 119380 KB Output is correct
18 Correct 195 ms 119512 KB Output is correct
19 Correct 304 ms 119632 KB Output is correct
20 Correct 292 ms 119348 KB Output is correct