답안 #1063786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1063786	2024-08-18T02:18:08 Z	Drifter24	원숭이와 사과 나무 (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

#	결과	실행 시간	메모리	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	-