Submission #31779

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31779	2017-09-08T13:12:51 Z	trath	Monkey and Apple-trees (IZhO12_apple)	C++	0 / 100	173 ms	2176 KB

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

0 / 100.0

#	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	9 ms	2176 KB	Output is correct
5	Correct	13 ms	2176 KB	Output is correct
6	Correct	13 ms	2176 KB	Output is correct
7	Correct	26 ms	2176 KB	Output is correct
8	Correct	73 ms	2176 KB	Output is correct
9	Runtime error	173 ms	2176 KB	Execution timed out (wall clock limit exceeded)
10	Halted	0 ms	0 KB	-