Submission #31772

# Submission time Handle Problem Language Result Execution time Memory
31772 2017-09-08T13:02:06 Z trath Monkey and Apple-trees (IZhO12_apple) C++11
0 / 100
99 ms 2176 KB
    #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 time Memory Grader output
1 Correct 0 ms 2176 KB Output is correct
2 Correct 0 ms 2176 KB Output is correct
3 Correct 0 ms 2176 KB Output is correct
4 Correct 13 ms 2176 KB Output is correct
5 Correct 6 ms 2176 KB Output is correct
6 Correct 3 ms 2176 KB Output is correct
7 Correct 13 ms 2176 KB Output is correct
8 Correct 56 ms 2176 KB Output is correct
9 Runtime error 99 ms 2176 KB Execution timed out (wall clock limit exceeded)
10 Halted 0 ms 0 KB -