Submission #1092087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1092087	2024-09-23T06:16:26 Z	vijaygomathinayagam	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	73708 KB

apple

#include<iostream>
#include<sstream>
#pragma GCC optimize("O3")

const int MAXN = 30 * 100000;
const int ASK_QUERY = 1;
const int UPDATE_QUERY = 2;

struct Node {
	int sum, l, r, tl, tr;
	bool lazy;

	Node() : sum(0), lazy(false), l(-1), r(-1) {}
};

Node segment_tree[MAXN];
int cnt = 2;

void extend(int node) {
	int mid = (segment_tree[node].tl + segment_tree[node].tr) / 2;
	if (segment_tree[node].l == -1) {
		segment_tree[node].l = cnt++;
		segment_tree[segment_tree[node].l].tl = segment_tree[node].tl;
		segment_tree[segment_tree[node].l].tr = mid;
	}
	if (segment_tree[node].r == -1) {
		segment_tree[node].r = cnt++;
		segment_tree[segment_tree[node].r].tl = mid + 1;
		segment_tree[segment_tree[node].r].tr = segment_tree[node].tr;
	}
}

void push_lazy(int node) {
	if (segment_tree[node].lazy) {
		segment_tree[node].sum = segment_tree[node].tr - segment_tree[node].tl + 1;
		extend(node);
		segment_tree[segment_tree[node].l].lazy = segment_tree[segment_tree[node].r].lazy = true;
		segment_tree[node].lazy = false;
	}
}

void update(int node, int l, int r) {
	push_lazy(node);
	if (segment_tree[node].tl >= l && segment_tree[node].tr <= r)
		segment_tree[node].lazy = true;
	else {
		int mid = (segment_tree[node].tl + segment_tree[node].tr) / 2;
		extend(node);
		if (l <= mid)
			update(segment_tree[node].l, l, r);
		if (r >= mid + 1)
			update(segment_tree[node].r, l, r);
		push_lazy(segment_tree[node].l);
		push_lazy(segment_tree[node].r);
		segment_tree[node].sum = segment_tree[segment_tree[node].l].sum
			+ segment_tree[segment_tree[node].r].sum;
	}
}

int query(int node, int l, int r) {
	push_lazy(node);
	if (segment_tree[node].tl >= l && segment_tree[node].tr <= r)
		return segment_tree[node].sum;
	else {
		int mid = (segment_tree[node].tl + segment_tree[node].tr) / 2;
		extend(node);
		if (l > mid)
			return query(segment_tree[node].r, l, r);
		if (r <= mid)
			return query(segment_tree[node].l, l, r);
		return query(segment_tree[node].l, l, r)
			+ query(segment_tree[node].r, l, r);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	int m;
	std::cin >> m;
	std::stringstream ss;

	segment_tree[1].tl = 1;
	segment_tree[1].tr = 1e9;

	for (int i = 0, c = 0; i < m; i++) {
		int d, x, y;
		std::cin >> d >> x >> y;
		if (d == ASK_QUERY) {
			c = query(1, x + c, y + c);
			ss << c << std::endl;
		}
		else if (d == UPDATE_QUERY)
			update(1, x + c, y + c);
	}
	std::cout << ss.str();
	return 0;
}

Compilation message

apple.cpp: In constructor 'Node::Node()':
apple.cpp:11:7: warning: 'Node::lazy' will be initialized after [-Wreorder]
   11 |  bool lazy;
      |       ^~~~
apple.cpp:10:11: warning:   'int Node::l' [-Wreorder]
   10 |  int sum, l, r, tl, tr;
      |           ^
apple.cpp:13:2: warning:   when initialized here [-Wreorder]
   13 |  Node() : sum(0), lazy(false), l(-1), r(-1) {}
      |  ^~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	71000 KB	Output is correct
2	Correct	24 ms	70740 KB	Output is correct
3	Correct	24 ms	70748 KB	Output is correct
4	Correct	30 ms	70900 KB	Output is correct
5	Correct	32 ms	71000 KB	Output is correct
6	Correct	33 ms	71004 KB	Output is correct
7	Correct	33 ms	71128 KB	Output is correct
8	Correct	88 ms	72444 KB	Output is correct
9	Correct	160 ms	73708 KB	Output is correct
10	Execution timed out	2041 ms	72912 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-