Submission #523066

#	Time	Username	Problem	Language	Result	Execution time	Memory
523066		danielliu04	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	562 ms	262148 KiB

apple

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

#include <bits/stdc++.h>
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 max_n = 1e9+1; // this is the maximum possible range of the values
const int init_left = 1, init_right = max_n;
int q;

struct Node{
	Node* l; Node* r;
	int sum, lazy, left, right; // left and right correspond to the interval
	Node() : l(nullptr), r(nullptr), sum(0), lazy(0), left(-1), right(-1) {};
	Node(int sum1, int left1, int right1) : sum(sum1), lazy(0), left(left1), right(right1), l(nullptr), r(nullptr) {};
};

// this is creating new left and right children
void extend(Node* node){
	if(node->left == node->right || node->l) return;
	int mid = (node->left + node->right) / 2;
	node->l = new Node(0, node->left, mid);
	node->r = new Node(0, mid+1, node->right);
};

void propagate(Node* node){
	if(node->lazy == 0) return;
	node->sum = node->right - node->left + 1;
	node->lazy = 0;
	if(node->left == node->right) return;
	node->l->lazy = node->r->lazy = 1;
}

void update(int x, int y, Node* node){
	if(x <= node->left && node->right <= y){
		node->lazy = 1;
	}
	else{
		// cout << node->left << ' ' << node->right << endl;
		int mid = (node->left + node->right) / 2;
		extend(node);
		propagate(node);
		if(x <= mid){
			update(x, y, node->l);
		}
		if(y >= mid + 1){
			update(x, y, node->r);
		}
		// cout << "here" << endl;
		extend(node->l); propagate(node->l); extend(node->r); propagate(node->r);
		// cout << "here" << endl;
		node->sum = node->l->sum + node->r->sum;
	}
}

int query(int x, int y, Node* node){
	extend(node);
	propagate(node);
	if(x <= node->left && node->right <= y){
		return node->sum;
	}
	else{
		int mid = (node->left + node->right) / 2;
		int res = 0;
		if(x <= mid){
			res += query(x, y, node->l);
		}
		if(y >= mid + 1){
			res += query(x, y, node->r);
		}
		return res;
	}
}

int main() {

	Node* root = new Node(0, init_left, init_right);

	cin >> q;

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

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

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

Compilation message (stderr)

apple.cpp: In constructor 'Node::Node(int, int, int)':
apple.cpp:19:23: warning: 'Node::right' will be initialized after [-Wreorder]
   19 |  int sum, lazy, left, right; // left and right correspond to the interval
      |                       ^~~~~
apple.cpp:18:8: warning:   'Node* Node::l' [-Wreorder]
   18 |  Node* l; Node* r;
      |        ^
apple.cpp:21:2: warning:   when initialized here [-Wreorder]
   21 |  Node(int sum1, int left1, int right1) : sum(sum1), lazy(0), left(left1), right(right1), l(nullptr), r(nullptr) {};
      |  ^~~~

• Subtask 1: 0 / 100