Submission #164996

#	Time	Username	Problem	Language	Result	Execution time	Memory
164996		shashwatchandra	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	787 ms	262144 KiB

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 / 100