Submission #1063782

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063782	2024-08-18T02:10:10 Z	Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	274 ms	262144 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;
	}

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

Subtask #1

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	348 KB	Output is correct
4	Correct	12 ms	8804 KB	Output is correct
5	Correct	14 ms	10524 KB	Output is correct
6	Correct	14 ms	10072 KB	Output is correct
7	Correct	21 ms	10580 KB	Output is correct
8	Correct	124 ms	77884 KB	Output is correct
9	Correct	229 ms	132688 KB	Output is correct
10	Correct	245 ms	148564 KB	Output is correct
11	Correct	264 ms	161360 KB	Output is correct
12	Correct	255 ms	166660 KB	Output is correct
13	Correct	247 ms	207116 KB	Output is correct
14	Correct	253 ms	209320 KB	Output is correct
15	Runtime error	274 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-