Submission #31771

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31771	2017-09-08T13:01:27 Z	trath	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	139 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;

int main(){
	ios_base::sync_with_stdio(false);
	node *tree = new node();
	
  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	13 ms	2176 KB	Output is correct
5	Correct	16 ms	2176 KB	Output is correct
6	Correct	9 ms	2176 KB	Output is correct
7	Correct	29 ms	2176 KB	Output is correct
8	Correct	93 ms	2176 KB	Output is correct
9	Correct	136 ms	2176 KB	Output is correct
10	Runtime error	139 ms	2176 KB	Execution timed out (wall clock limit exceeded)
11	Halted	0 ms	0 KB	-