Submission #523078

#	Time	Username	Problem	Language	Result	Execution time	Memory
523078		danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	557 ms	206384 KiB

apple

// Link: https://oj.uz/problem/view/IZhO12_apple

#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
using namespace std;

#define ll long long
#define ld long double
// #define lc (node<<1)+1
// #define rc (node<<1)+2
#define endl '\n'
#define INF 1e18

const int init_left = 1;
const int init_right = 1e9+1;
int q;

struct Node{
	int left, mid, right, sum = 0, lazy = 0;
	Node *lc = 0, *rc = 0;
	Node(int l, int r) : left(l), right(r), mid((l+r)/2) {}

	void mod_lazy(int v){ // modify first, then store the lazy value (indicating that needs to pushed down)
		if(v == 0) return;
		sum = right - left + 1;
		lazy = v;
	}

	void propagate(){
		if(!lc) lc = new Node(left, mid);
		if(!rc) rc = new Node(mid+1, right);
		lc->mod_lazy(lazy); rc->mod_lazy(lazy);
		lazy = 0;
	}

	int query(int x, int y){
		if(x <= left && right <= y) return sum;
		propagate(); // push down to the two children
		int res = 0;
		if(x <= mid) res += lc->query(x, y);
		if(y >= mid + 1) res += rc->query(x, y);
		return res;
	}

	void update(int x, int y){
		if(x <= left && right <= y) mod_lazy(1); // add a 1 lazy tag to this node
		else{
			propagate();
			if(x <= mid) lc->update(x, y);
			if(y >= mid+1) rc->update(x, y);
			sum = lc->sum + rc->sum;
		}
	}
};

int main() {

	cin >> q;

	Node root(init_left, init_right);

	int c = 0;
	while(q --){

		int type, a, b; cin >> type >> a >> b;

		if(type == 1){
			c = root.query(a + c, b + c);
			cout << c << endl;
		}
		else{
			root.update(a + c, b + c);
		}
	}
}	

Compilation message (stderr)

apple.cpp: In constructor 'Node::Node(int, int)':
apple.cpp:19:17: warning: 'Node::right' will be initialized after [-Wreorder]
   19 |  int left, mid, right, sum = 0, lazy = 0;
      |                 ^~~~~
apple.cpp:19:12: warning:   'int Node::mid' [-Wreorder]
   19 |  int left, mid, right, sum = 0, lazy = 0;
      |            ^~~
apple.cpp:21:2: warning:   when initialized here [-Wreorder]
   21 |  Node(int l, int r) : left(l), right(r), mid((l+r)/2) {}
      |  ^~~~

• Subtask 1: 100 / 100