Submission #31778

#TimeUsernameProblemLanguageResultExecution timeMemory
31778trathMonkey and Apple-trees (IZhO12_apple)C++98
0 / 100
183 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...