제출 #31780

#제출 시각아이디문제언어결과실행 시간메모리
31780trath원숭이와 사과 나무 (IZhO12_apple)C++98
0 / 100
149 ms2176 KiB
            #include <bits/stdc++.h>
             
            using namespace std;
             
            struct node {
            	int sum;
            	struct node *left, *right;
            	node(){
            		sum = 0;
            		left = NULL;
            		right = NULL;
            	}
            };
             
            void combine(node *root, node *a, node *b){
            	root->sum= 0;
            	if(a != NULL) root->sum += a->sum;
            	if(b != NULL) root->sum += b->sum;
            }
             
            void update(node *root, int l, int r, int a, int b){
            	if(root->sum == r-l+1) return;
            	if(l == a && r == b){
            		root->sum=(r-l+1);
            		return;
            	}
            	int m = (l+r) >> 1;
            	if(b <= m){
            		if(!root->left) root->left = new node();
            		update(root->left, l, m, a, b);
            	}
            	else if(m < a){
            		if(!root->right) root->right = new node();
            		update(root->right, m+1, r, a, b);
            	}
            	else {
            		if(!root->left) root->left = new node();
            		if(!root->right) root->right = new node();
            		update(root->left, l, m, a, m);
            		update(root->right, m+1, r, m+1, b);
            		
            	}
            	combine(root, root->left, root->right);
            }
             
            int query(node *root, int l, int r, int a, int b){
            	if(root->sum == r-l+1) return b-a+1;
            	if(l == a && r == b) return root->sum;
            	int m = (l+r) >> 1;
            	if(b <= m){
            		if(root->left) return query(root->left, l, m, a, b);
            		else return 0;
            	}
            	else if(m < a){
            		if(root->right) return query(root->right, m+1, r, a, b);
            		else return 0;
            	}
            	else {
            		int sum = 0;
            		if(root->left) sum += query(root->left, l, m, a, m);
            		if(root->right) sum += query(root->right, m+1, r, m+1, b);
            		return sum;
            	}
            }
             
            int c = 0;
                 	node *tree = new node();
         
            int main(){
            	ios_base::sync_with_stdio(false);
            	
              int q;
            	cin >> q;
            	while(q--){
            		int op,a,b;
            		cin >> op >> a >> b;
            		if(op == 1){
            			c = query(tree, 1, (int)1e9, a+c, b+c);
            			cout << c << endl;
            		}
            		else update(tree, 1, (int)1e9, a+c, b+c);
            	}
            }
#Verdict Execution timeMemoryGrader output
Fetching results...