Submission #988891

#	Time	Username	Problem	Language	Result	Execution time	Memory
988891		holagola	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	0 ms	348 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define print(arr) for(auto& x:arr)cout<<x<<" ";cout<<"\n"
#define watch(x) cout<<#x<<"="<<x<<"\n"
#define all(x) x.begin(), x.end()
#define sz(x) ((int) x.size())
#define PB push_back
#define S second
#define F first
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

int oper(int x, int y){
	return x+y;
}

struct Node {
	int lz, lzL, lzR, val;
	Node *L, *R;
	Node(int lz = 0) : lz(lz), lzL(0), lzR(0), val(0), L(0), R(0) {}
	void propagate(int l, int r) {
		if(lz) {
			if(l != r) {
				if(L) L->lz = oper(L->lz, lz);
				else lzL = oper(lzL, lz);
				if(R) R->lz = oper(R->lz, lz);
				else lzR = oper(lzR, lz);
			}
			val = (r-l+1)*lz;
			lz = 0;
		}
	}
};

int null = 0;
int get_val(Node* root, int lz, int a, int b) {
	if(!root) return lz*(b-a+1);
	return root->val;
}

struct SegTree { 
	Node* root;
	int n;
	SegTree(int n) : n(n), root(new Node()) {}

	void update(Node* &root, int a, int b, int l, int r, int x, int lz = 0) {
		if((l > b || r < a) && !root) return; // break condition, this line optimizes memory
		if(root == nullptr) root = new Node(lz);
		root->propagate(l, r);
		if(l > b || r < a) return; 
		if(a <= l && r <= b) { 
			root->lz = oper(root->lz, x);
			root->propagate(l, r);
		} else {
			int m = (l+r) >> 1;
			update(root->L, a, b, l, m, x, root->lzL);
			update(root->R, a, b, m+1, r, x, root->lzR);
			root->val = oper(get_val(root->L, root->lzL, l, m),get_val(root->R, root->lzR, m+1, r));
		}
	}

	int get(Node* root, int a, int b, int l, int r, int lz = 0) {
		if(l > b || r < a) return null;
		if(root) root->propagate(l, r);
		if((a <= l && r <= b) || !root) { 
			return get_val(root, lz, l, r);
		} else {
			int m = (l+r) >> 1;
			return oper(get(root->L, a, b, l, m, root->lzL), get(root->R, a, b, m+1, r, root->lzR));
		}
	}

	void update(int a, int b, int x) { update(root, a, b, 0, n-1, x); }
	int get(int a, int b) { return get(root, a, b, 0, n-1); }
};


int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	SegTree st(1e9);
	int q;cin>>q;
	int op,l,r,c=0;
	while(q--){
		cin>>op>>l>>r;
		l--;r--;
		if(op==1){
			c=st.get(l+c,r+c);
			cout<<c<<"\n";
		}else{
			st.update(l+c,r+c,1);
		}
	}
	return 0;
}

Compilation message (stderr)

apple.cpp: In constructor 'SegTree::SegTree(int)':
apple.cpp:46:6: warning: 'SegTree::n' will be initialized after [-Wreorder]
   46 |  int n;
      |      ^
apple.cpp:45:8: warning:   'Node* SegTree::root' [-Wreorder]
   45 |  Node* root;
      |        ^~~~
apple.cpp:47:2: warning:   when initialized here [-Wreorder]
   47 |  SegTree(int n) : n(n), root(new Node()) {}
      |  ^~~~~~~

• Subtask 1: 0 / 100