Submission #993444

#	Time	Username	Problem	Language	Result	Execution time	Memory
993444		Drifter24	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	363 ms	166260 KiB

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 (stderr)

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