제출 #31774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31774		trath	원숭이와 사과 나무 (IZhO12_apple)	C++98	100 / 100	176 ms	2176 KiB

apple

    #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);
    	}
    }

• Subtask 1: 100 / 100