Submission #1063790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063790	2024-08-18T02:38:23 Z	Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	336 ms	205468 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	9 ms	4992 KB	Output is correct
5	Correct	13 ms	5980 KB	Output is correct
6	Correct	12 ms	5784 KB	Output is correct
7	Correct	11 ms	5976 KB	Output is correct
8	Correct	92 ms	43824 KB	Output is correct
9	Correct	183 ms	75672 KB	Output is correct
10	Correct	184 ms	83536 KB	Output is correct
11	Correct	196 ms	89976 KB	Output is correct
12	Correct	205 ms	92756 KB	Output is correct
13	Correct	184 ms	108116 KB	Output is correct
14	Correct	209 ms	109140 KB	Output is correct
15	Correct	279 ms	199764 KB	Output is correct
16	Correct	275 ms	201076 KB	Output is correct
17	Correct	203 ms	112716 KB	Output is correct
18	Correct	236 ms	112812 KB	Output is correct
19	Correct	336 ms	205392 KB	Output is correct
20	Correct	292 ms	205468 KB	Output is correct