Submission #969369

#	Time	Username	Problem	Language	Result	Execution time	Memory
969369		tamir1	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	340 ms	262144 KiB

apple

#include<bits/stdc++.h>
#define ll int
using namespace std;
ll m,i,x,y,d,c,ans;
struct node{
	node *le,*ri;
	ll val,lazy,l,r;
	void create(ll x,ll y){
		val=0;
		lazy=0;
		l=x;
		r=y;
		le=NULL;
		ri=NULL;
	}
	void fix(){          
		if(l==r){
			if(lazy==1) val=1;
			return;
		}
		ll mid=(l+r)/2;
		if(le==NULL){
			le=new node;
			le->le=NULL;
			le->ri=NULL;
			le->l=l;
			le->r=mid;
			le->lazy=0;
			le->val=0;
		}
		if(ri==NULL){
			ri=new node;
			ri->le=NULL;
			ri->ri=NULL;
			ri->l=mid+1;
			ri->r=r;
			ri->lazy=0;
			ri->val=0;
		}
		if(lazy==1){
			val=r-l+1;
			le->lazy=1;
			ri->lazy=1;
			lazy=0;
		}
	}
	ll query(ll x,ll y){
		fix();
		if(l>y || r<x) return 0;
		if(l>=x && r<=y) return val;
		return le->query(x,y)+ri->query(x,y);
	}
	void update(ll x,ll y){
		fix();
		if(l>y || r<x) return;
		if(l>=x && r<=y){
			val=r-l+1;
			if(l!=r){
				le->lazy=1;
				ri->lazy=1;
			}
			return;
		}
		le->update(x,y);
		ri->update(x,y);
		val=le->val+ri->val;
	}
} s;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> m;
	s.create(1,1e9);
	for(i=1;i<=m;i++){
		cin >> d >> x >> y;
		if(d==1){
			ans=s.query(x+c,y+c);
			cout << ans << "\n";
			c=ans;
		}
		else{
			s.update(x+c,y+c);
		}
	}
}

• Subtask 1: 0 / 100