oj.uz

Submission #523068

# Submission time Handle Problem Language Result Execution time Memory
523068 2022-02-06T21:06:05 Z danielliu04 Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 484 ms 262148 KB 
// 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 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:20:23: warning: 'Node::right' will be initialized after [-Wreorder]
   20 |  int sum, lazy, left, right; // left and right correspond to the interval
      |                       ^~~~~
apple.cpp:19:8: warning:   'Node* Node::l' [-Wreorder]
   19 |  Node* l; Node* r;
      |        ^
apple.cpp:22:2: warning:   when initialized here [-Wreorder]
   22 |  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 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 26 ms 7684 KB Output is correct
5 Correct 32 ms 9188 KB Output is correct
6 Correct 28 ms 8928 KB Output is correct
7 Correct 31 ms 9148 KB Output is correct
8 Correct 236 ms 69300 KB Output is correct
9 Correct 436 ms 118316 KB Output is correct
10 Correct 435 ms 132508 KB Output is correct
11 Correct 469 ms 143476 KB Output is correct
12 Correct 450 ms 148200 KB Output is correct
13 Correct 438 ms 181376 KB Output is correct
14 Correct 429 ms 183428 KB Output is correct
15 Runtime error 484 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -