oj.uz

Submission #523078

# Submission time Handle Problem Language Result Execution time Memory
523078 2022-02-07T02:18:52 Z danielliu04 Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 557 ms 206384 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 22 ms 4908 KB Output is correct
5 Correct 25 ms 5988 KB Output is correct
6 Correct 25 ms 5728 KB Output is correct
7 Correct 27 ms 5980 KB Output is correct
8 Correct 171 ms 43980 KB Output is correct
9 Correct 342 ms 75852 KB Output is correct
10 Correct 422 ms 83896 KB Output is correct
11 Correct 361 ms 90348 KB Output is correct
12 Correct 401 ms 93032 KB Output is correct
13 Correct 356 ms 108408 KB Output is correct
14 Correct 356 ms 109304 KB Output is correct
15 Correct 517 ms 200316 KB Output is correct
16 Correct 508 ms 201964 KB Output is correct
17 Correct 360 ms 113424 KB Output is correct
18 Correct 356 ms 113632 KB Output is correct
19 Correct 557 ms 206276 KB Output is correct
20 Correct 539 ms 206384 KB Output is correct