Submission #1063789

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063789	2024-08-18T02:37:58 Z	Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	362 ms	207804 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	4956 KB	Output is correct
5	Correct	12 ms	6100 KB	Output is correct
6	Correct	12 ms	5980 KB	Output is correct
7	Correct	16 ms	5980 KB	Output is correct
8	Correct	90 ms	44496 KB	Output is correct
9	Correct	185 ms	77320 KB	Output is correct
10	Correct	194 ms	85196 KB	Output is correct
11	Correct	189 ms	91800 KB	Output is correct
12	Correct	201 ms	94544 KB	Output is correct
13	Correct	184 ms	110160 KB	Output is correct
14	Correct	181 ms	111188 KB	Output is correct
15	Correct	301 ms	201808 KB	Output is correct
16	Correct	283 ms	203440 KB	Output is correct
17	Correct	190 ms	114772 KB	Output is correct
18	Correct	187 ms	114836 KB	Output is correct
19	Correct	293 ms	207700 KB	Output is correct
20	Correct	362 ms	207804 KB	Output is correct