Submission #164996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
164996	2019-11-24T15:57:26 Z	shashwatchandra	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	787 ms	262144 KB

apple

/*input
6
2 1 7
2 10 12
1 7 11
2 11 13
1 8 10
1 15 17
*/
#include <iostream> 
using namespace std;

struct node{
	node* left,*right;
	int cnt;
	bool lazy = 0;
	node(){
		cnt = 0;
		lazy = 0;
		left = NULL;
		right = NULL;
	}
	void extend(){
		left = new node();
		right = new node();
	}
};
 
node* root = new node();
 
#define mid (l+r)/2
 
void upd(node* cur,int l,int r,int start,int end){
	if(cur->lazy)cur->cnt = r-l+1;
	if(l != r and cur->lazy){
		if(cur->left == NULL)cur->extend();
		cur->left->lazy = 1;
		cur->right->lazy = 1;
	}
	cur->lazy = 0;
	if(l > end or start > r)return;
	if(start<= l and r <= end){
		if(cur->cnt == r-l+1)return;
		cur->lazy = 1;
		if(cur->lazy)cur->cnt = r-l+1;
		if(l != r and cur->lazy){
			if(cur->left == NULL)cur->extend();
			cur->left->lazy = 1;
			cur->right->lazy = 1;
		}
		cur->lazy = 0;
		return;
	}
	if(cur->left == NULL)cur->extend();
	upd(cur->left,l,mid,start,end);
	upd(cur->right,mid+1,r,start,end);
	cur->cnt = cur->left->cnt+cur->right->cnt;
}
 
int query(node *cur,int l,int r,int start,int end){
	if(cur->lazy)cur->cnt = r-l+1;
	if(l != r and cur->lazy){
		if(cur->left == NULL)cur->extend();
		cur->left->lazy = 1;
		cur->right->lazy = 1;
	}
	cur->lazy = 0;
	if(l > end or start > r)return 0;
	if(start<= l and r <= end){
		return cur->cnt;
	}
	if(cur->left == NULL)cur->extend();
	return query(cur->left,l,mid,start,end)+
	query(cur->right,mid+1,r,start,end);
}
 
int upper = 1e9;
int q;
int c = 0;
 
void solve(){
  	cin >> q;
  	while(q--){
  		int ty,x,y;cin >> ty >> x >> y;
  		x += c;
  		y += c;
  		if(ty == 2){
  			upd(root,1,upper,x,y);
  		}
  		else{
  			int ans =query(root,1,upper,x,y);
  			cout << ans << "\n";
  			c = ans;
  		}
  	}
}
 
signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	22 ms	5880 KB	Output is correct
5	Correct	28 ms	7036 KB	Output is correct
6	Correct	27 ms	6904 KB	Output is correct
7	Correct	32 ms	7004 KB	Output is correct
8	Correct	211 ms	51576 KB	Output is correct
9	Correct	445 ms	87612 KB	Output is correct
10	Correct	445 ms	98296 KB	Output is correct
11	Correct	460 ms	106628 KB	Output is correct
12	Correct	459 ms	110376 KB	Output is correct
13	Correct	449 ms	137080 KB	Output is correct
14	Correct	457 ms	138384 KB	Output is correct
15	Correct	772 ms	254712 KB	Output is correct
16	Correct	766 ms	256832 KB	Output is correct
17	Correct	472 ms	145644 KB	Output is correct
18	Correct	453 ms	145656 KB	Output is correct
19	Correct	787 ms	262144 KB	Output is correct
20	Correct	787 ms	262144 KB	Output is correct