Submission #1063789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063789		Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	362 ms	207804 KiB

apple

#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;
	}
};

typedef Node* PNode;
void update(PNode x){
	if(x->r-x->l==1)return;
	x->val=oper(x->pl->val, x->pr->val);
}

void extends(PNode x){
	if(x->r-x->l!=1 && !x->pl){
		int m=(x->r+x->l)/2;
		x->pl=new Node(x->l, m);
		x->pr=new Node(m, x->r);
	}
}

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

struct SegTree{
	PNode root;

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

	T get(PNode x, int l, int r){
		int lx=x->l,rx=x->r;
		if(lx>=r || l>=rx)return null;
		if(lx>=l && rx<=r)return x->val;
		extends(x);
        propagate(x);
		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;
	T ans=0,op,l,r;
	SegTree st;
	st.build(1,1e9);
	while(q--){
		cin>>op>>l>>r;
		l+=ans;
		r+=ans;
		if(op==1ll){
			ans=st.get(l,r);
			cout<<ans<<"\n";
		}else{
			st.upd(l,r,1ll);
		}
	}
	return 0;
}

• Subtask 1: 100 / 100