답안 #993446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993446	2024-06-05T16:43:22 Z	Drifter24	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	267 ms	116948 KB

apple

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node{
	int sum,l,r,ptr,ptrl,ptrr;
};

struct SegTree{
	vector<Node> vals;
	vector<int> lazy;
	int null=0;

	void oper(int x){
		vals[x].sum=vals[vals[x].ptrl].sum+vals[vals[x].ptrr].sum;
	}

	void extends(int x){
		if(vals[x].r-vals[x].l==1)return;
		int m=vals[x].l+(vals[x].r-vals[x].l)/2;
		if(vals[x].ptrl==-1){
			vals[x].ptrl=vals.size();
			vals.push_back({0,vals[x].l,m,vals[x].ptrl,-1,-1});
			lazy.push_back(0);
		}
		if(vals[x].ptrr==-1){
			vals[x].ptrr=vals.size();
			vals.push_back({0,m,vals[x].r,vals[x].ptrr,-1,-1});
			lazy.push_back(0);
		}
	}

	void build(int n){
		vals.push_back({0,1,n+1,0,-1,-1});
		lazy.push_back(0);
	}

    void propagate(int x){
		if(vals[x].r-vals[x].l==1)return;
        if(lazy[x]==0)return;
		extends(x);
		int m=vals[x].l+(vals[x].r-vals[x].l)/2;
		lazy[vals[x].ptrl]=1;
		lazy[vals[x].ptrr]=1;
		vals[vals[x].ptrl].sum=(m-vals[x].l);
		vals[vals[x].ptrr].sum=(vals[x].r-m);
		lazy[x]=0;
    }

    void upd(int l, int r, int x){
        propagate(x);
		int lx=vals[x].l, rx=vals[x].r;
		if(lx>=r || l>=rx)return;
		if(lx>=l && rx<=r){
            lazy[x]=1;
			vals[x].sum=(rx-lx);
            return;
        }
		extends(x);
		upd(l,r,vals[x].ptrl);
		upd(l,r,vals[x].ptrr);
		oper(x);
	}

	int get(int l, int r, int x){
        propagate(x);
		int lx=vals[x].l, rx=vals[x].r;
		if(lx>=r || l>=rx)return null;
		if(lx>=l && rx<=r)return vals[x].sum;
		extends(x);
		int v1=get(l,r,vals[x].ptrl);
		int v2=get(l,r,vals[x].ptrr);
		return v1+v2;
	}

	void upd(int l, int r){upd(l,r+1,0);}
	int get(int l, int r){return get(l,r+1,0);}
};

int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int q;
	cin>>q;
	SegTree st;
	st.build(1e7);
	int t,l,r;
	int c=0;
	while(q--){
		cin>>t>>l>>r;
		if(t==1){
			c=st.get(c+l,c+r);
			cout<<c<<"\n";
		}else{
			st.upd(c+l,c+r);
		}
	}
	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	1 ms	348 KB	Output is correct
4	Correct	14 ms	7928 KB	Output is correct
5	Correct	16 ms	8688 KB	Output is correct
6	Correct	21 ms	8304 KB	Output is correct
7	Correct	15 ms	9200 KB	Output is correct
8	Correct	105 ms	59088 KB	Output is correct
9	Correct	242 ms	116948 KB	Output is correct
10	Correct	250 ms	116672 KB	Output is correct
11	Correct	267 ms	116708 KB	Output is correct
12	Correct	264 ms	116420 KB	Output is correct
13	Incorrect	25 ms	4556 KB	Output isn't correct
14	Halted	0 ms	0 KB	-