Submission #993446

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
993446	2024-06-05T16:43:22 Z	Drifter24	Monkey and Apple-trees (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

#	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	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	-