답안 #870654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870654	2023-11-08T17:32:56 Z	Irate	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	334 ms	190816 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int mxN = 16e6;
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);	
		}
	}
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	190036 KB	Output is correct
2	Correct	23 ms	190112 KB	Output is correct
3	Correct	27 ms	190032 KB	Output is correct
4	Correct	34 ms	190304 KB	Output is correct
5	Correct	36 ms	190288 KB	Output is correct
6	Correct	37 ms	190296 KB	Output is correct
7	Correct	35 ms	190292 KB	Output is correct
8	Correct	102 ms	190300 KB	Output is correct
9	Correct	199 ms	190816 KB	Output is correct
10	Correct	235 ms	190628 KB	Output is correct
11	Correct	226 ms	190592 KB	Output is correct
12	Correct	242 ms	190608 KB	Output is correct
13	Correct	209 ms	190676 KB	Output is correct
14	Correct	202 ms	190572 KB	Output is correct
15	Correct	302 ms	190652 KB	Output is correct
16	Correct	309 ms	190552 KB	Output is correct
17	Correct	235 ms	190684 KB	Output is correct
18	Correct	219 ms	190704 KB	Output is correct
19	Correct	310 ms	190648 KB	Output is correct
20	Correct	334 ms	190700 KB	Output is correct