Submission #1063782

#TimeUsernameProblemLanguageResultExecution timeMemory
1063782Drifter24Monkey and Apple-trees (IZhO12_apple)C++14
0 / 100
274 ms262144 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long T;
T null=0, noVal=0;
T oper(T a, T b){return a+b;}

struct Node{
	T val,lz;
	int l,r;
	Node *pl,*pr;
	Node(int ll, int rr){
		val=null;lz=noVal;
		pl=pr=nullptr;
		l=ll;r=rr;
	}

	void update(){
		val=oper(pl->val, pr->val);
	}

	void extends(){
		if(r-l==1)return;
		if(pl)return;
		int m=l+(r-l)/2;
		pl=new Node(l, m);
		pr=new Node(m, r);
	}

	void propagate(){
		if(r-l==1)return;
        if(lz==noVal)return;
		extends();
		int m=l+(r-l)/2;
		pl->lz=lz;
		pl->val=m-l;
		pr->lz=lz;
		pr->val=r-m;
		lz=noVal;
	}
};

typedef Node* PNode;
struct SegTree{
	PNode root;

    void upd(PNode x, int l, int r, T v){
        x->propagate();
		int lx=x->l,rx=x->r;
		if(lx>=r || l>=rx)return;
		if(lx>=l && rx<=r){
            x->lz=v;
			x->val=rx-lx;
            return;
        }
		x->extends();
		upd(x->pl,l,r,v);
		upd(x->pr,l,r,v);
		x->update();
	}

	T get(PNode x, int l, int r){
		x->propagate();
		int lx=x->l,rx=x->r;
		if(lx>=r || l>=rx)return null;
		if(lx>=l && rx<=r)return x->val;
		x->extends();
		T v1=get(x->pl,l,r);
		T v2=get(x->pr,l,r);
		return oper(v1,v2);
	}

	void upd(int l, int r, T v){upd(root,l,r+1,v);}
	T get(int l, int r){return get(root,l,r+1);}
	void build(int l, int r){root=new Node(l, r+1);}
};

int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int q;
	cin>>q;
	int ans=0,op,l,r;
	SegTree st;
	st.build(1,1e9);
	while(q--){
		cin>>op>>l>>r;
		l+=ans;
		r+=ans;
		if(op==1){
			ans=st.get(l,r);
			cout<<ans<<"\n";
		}else{
			st.upd(l,r,1);
		}
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...