Submission #993448

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
993448	2024-06-05T16:44:33 Z	Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	454 ms	262144 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(1e9);
	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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	14 ms	9224 KB	Output is correct
5	Correct	16 ms	9220 KB	Output is correct
6	Correct	16 ms	8688 KB	Output is correct
7	Correct	15 ms	9456 KB	Output is correct
8	Correct	116 ms	59224 KB	Output is correct
9	Correct	252 ms	115520 KB	Output is correct
10	Correct	270 ms	115444 KB	Output is correct
11	Correct	286 ms	115392 KB	Output is correct
12	Correct	275 ms	115392 KB	Output is correct
13	Correct	344 ms	230544 KB	Output is correct
14	Correct	321 ms	232584 KB	Output is correct
15	Correct	451 ms	256104 KB	Output is correct
16	Correct	437 ms	257816 KB	Output is correct
17	Correct	316 ms	232584 KB	Output is correct
18	Correct	311 ms	232628 KB	Output is correct
19	Correct	447 ms	262144 KB	Output is correct
20	Correct	454 ms	262144 KB	Output is correct