oj.uz

Submission #523066

# Submission time Handle Problem Language Result Execution time Memory
523066 2022-02-06T21:03:13 Z danielliu04 Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 562 ms 262148 KB 
// 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 29 ms 7692 KB Output is correct
5 Correct 32 ms 9468 KB Output is correct
6 Correct 35 ms 9088 KB Output is correct
7 Correct 31 ms 9368 KB Output is correct
8 Correct 217 ms 70144 KB Output is correct
9 Correct 446 ms 120060 KB Output is correct
10 Correct 473 ms 134248 KB Output is correct
11 Correct 529 ms 145292 KB Output is correct
12 Correct 486 ms 149956 KB Output is correct
13 Correct 562 ms 183344 KB Output is correct
14 Correct 490 ms 185388 KB Output is correct
15 Runtime error 523 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -