답안 #889064

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
889064 2023-12-18T18:18:55 Z shadow_sami 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
75 ms 46740 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<=1e6);
	}
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 14 ms 4956 KB Output is correct
5 Correct 21 ms 5972 KB Output is correct
6 Correct 17 ms 5724 KB Output is correct
7 Correct 18 ms 5912 KB Output is correct
8 Runtime error 75 ms 46740 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -