Submission #993444

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
993444	2024-06-05T16:38:13 Z	Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	363 ms	166260 KB

apple

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

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

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

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

	void extends(int x){
		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){
		size=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]|=lazy[x];
		lazy[vals[x].ptrr]|=lazy[x];
		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, ll v,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;
        }
		int m=(lx+rx)/2;
		extends(x);
		upd(l,r,v,vals[x].ptrl);
		upd(l,r,v,vals[x].ptrr);
		oper(x);
	}

	ll 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);
		ll v1=get(l,r,vals[x].ptrl);
		ll v2=get(l,r,vals[x].ptrr);
		return v1+v2;
	}

	void upd(int l, int r, ll v){upd(l,r+1,v,0);}
	ll 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;
	ll 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,1);
		}
	}
	return 0;
}

Compilation message

apple.cpp: In member function 'void SegTree::upd(int, int, ll, int)':
apple.cpp:61:7: warning: unused variable 'm' [-Wunused-variable]
   61 |   int m=(lx+rx)/2;
      |       ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	17 ms	10860 KB	Output is correct
5	Correct	25 ms	11012 KB	Output is correct
6	Correct	20 ms	10764 KB	Output is correct
7	Correct	19 ms	10824 KB	Output is correct
8	Correct	160 ms	83056 KB	Output is correct
9	Correct	352 ms	166260 KB	Output is correct
10	Correct	355 ms	165948 KB	Output is correct
11	Correct	354 ms	165756 KB	Output is correct
12	Correct	363 ms	165720 KB	Output is correct
13	Incorrect	30 ms	5636 KB	Output isn't correct
14	Halted	0 ms	0 KB	-