Submission #1063786

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063786	2024-08-18T02:18:08 Z	Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	276 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(){
		if(r-l==1)return;
		val=oper(pl->val, pr->val);
	}

	void extends(){
		if(r-l!=1 && !pl){
			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=1;
		pl->val=m-l;
		pr->lz=1;
		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=1;
			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;
	T 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	1 ms	344 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	8860 KB	Output is correct
5	Correct	14 ms	10588 KB	Output is correct
6	Correct	14 ms	10180 KB	Output is correct
7	Correct	14 ms	10536 KB	Output is correct
8	Correct	120 ms	77784 KB	Output is correct
9	Correct	235 ms	132396 KB	Output is correct
10	Correct	248 ms	148344 KB	Output is correct
11	Correct	258 ms	160948 KB	Output is correct
12	Correct	261 ms	166224 KB	Output is correct
13	Correct	249 ms	207188 KB	Output is correct
14	Correct	254 ms	209232 KB	Output is correct
15	Runtime error	276 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-