답안 #889065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
889065 2023-12-18T18:19:14 Z shadow_sami 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
399 ms 207700 KB
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair<int,int>
#define left t->l,l,(l + r)/2
#define right t->r,(l + r)/2 + 1,r
using namespace std;
 
const int inf = 1000000000;
 ll cnt = 0;
struct Node {
    ll s,lz;
    Node *l, *r;
    Node() : s(0), lz(0), l(NULL), r(NULL) { }
};
 
void children(Node *t){
	cnt++;
	if (!(t->l)) t->l = new Node();
	if (!(t->r)) t->r = new Node();
}
void push(Node *t,int l,int r){
	if ((t -> lz) == 0) return;
 
	int k = t -> lz;
	(t -> l) -> lz = k;
	(t -> l) -> s = (l + r)/2 - l + 1;
	
	(t -> r) -> lz = k;
	(t -> r) -> s = r - (l + r)/2;
 
	(t -> lz) = 0;
}
 
void upd(Node *t,int l,int r,int L,int R){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t -> s = (r - l + 1);
		t -> lz = 1;
		return;
	}
 
	if (!t->l) t->l = new Node();
	if (!t->r) t->r = new Node();
 
	children(t);
	push(t,l,r);
	upd(left,L,R);
	upd(right,L,R);
	t->s = (t->l)->s + (t->r)->s;
}
 
int get(Node *t,int l,int r,int L,int R){
	if (t==NULL || r < L || R < l) return 0;
	if (L <= l && r <= R) return t->s;
 
	children(t);
	push(t,l,r);
	return get(left,L,R) + get(right,L,R);
}
 
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int q,c = 0;
	cin>>q;
 
	Node *root = new Node();
 
	while (q--){
		int tp,l,r;
		cin>>tp>>l>>r;
		l += c;
		r += c;
 
		if (tp == 1){
			c = get(root,1,inf,l,r);
			cout<<c<<endl;
		}else{
			upd(root,1,inf,l,r);

		}
		assert(cnt<=1e7);
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 14 ms 4932 KB Output is correct
5 Correct 18 ms 5980 KB Output is correct
6 Correct 17 ms 5720 KB Output is correct
7 Correct 23 ms 5976 KB Output is correct
8 Correct 118 ms 43824 KB Output is correct
9 Correct 260 ms 76028 KB Output is correct
10 Correct 262 ms 83540 KB Output is correct
11 Correct 258 ms 89968 KB Output is correct
12 Correct 272 ms 92844 KB Output is correct
13 Correct 246 ms 108112 KB Output is correct
14 Correct 254 ms 109080 KB Output is correct
15 Correct 369 ms 201620 KB Output is correct
16 Correct 390 ms 203112 KB Output is correct
17 Correct 266 ms 114772 KB Output is correct
18 Correct 257 ms 114744 KB Output is correct
19 Correct 369 ms 207616 KB Output is correct
20 Correct 399 ms 207700 KB Output is correct