Submission #21879

# Submission time Handle Problem Language Result Execution time Memory
21879 2017-04-26T15:17:20 Z ulna Monkey and Apple-trees (IZhO12_apple) C++11
100 / 100
466 ms 138244 KB
#include <bits/stdc++.h>
using namespace std;

// why am I so weak

int m;

struct node {
	int sum;
	int lazy;
	node *left, *right;

	node(int sum) : sum(sum), lazy(-1) {left = right = NULL;}
} *root = new node(0);

void push(node *u, int x, int y) {
	if (u->lazy < 0) return;

	int mid = (x + y) >> 1;

	u->left->lazy = u->right->lazy = 1;

	u->left->sum = mid - x + 1;
	u->right->sum = y - mid;

	u->lazy = -1;
}
int query(node *u, int x, int y, int l, int r) {
	if (!u) return 0;
	if (l > y || r < x) return 0;

	if (l <= x && y <= r) return u->sum;

	int mid = (x + y) >> 1;

	if (!u->left) u->left = new node(0);
	if (!u->right) u->right = new node(0);

	push(u, x, y);

	return query(u->left, x, mid, l, r) + query(u->right, mid + 1, y, l, r);
}
void update(node *u, int x, int y, int l, int r) {
	if (l > y || r < x) return;

	if (l <= x && y <= r) {
		u->sum = y - x + 1;
		u->lazy = 1;
		return;
	}

	int mid = (x + y) >> 1;

	if (!u->left) u->left = new node(0);
	if (!u->right) u->right = new node(0);

	push(u, x, y);

	update(u->left, x, mid, l, r);
	update(u->right, mid + 1, y, l, r);

	u->sum = u->left->sum + u->right->sum;
}
int main() {
	scanf("%d", &m);

	int c = 0;

	while (m--) {
		int ope, x, y;
		scanf("%d %d %d", &ope, &x, &y);
		x += c, y += c;

		if (ope == 1) {
			printf("%d\n", c = query(root, 1, (int)1e9, x, y));
		} else {
			update(root, 1, (int)1e9, x, y);
		}
	}

	return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
                 ^
apple.cpp:71:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &ope, &x, &y);
                                  ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Correct 0 ms 2020 KB Output is correct
4 Correct 13 ms 5056 KB Output is correct
5 Correct 13 ms 5716 KB Output is correct
6 Correct 9 ms 5584 KB Output is correct
7 Correct 16 ms 5716 KB Output is correct
8 Correct 136 ms 30796 KB Output is correct
9 Correct 299 ms 51916 KB Output is correct
10 Correct 329 ms 57196 KB Output is correct
11 Correct 299 ms 61420 KB Output is correct
12 Correct 293 ms 63268 KB Output is correct
13 Correct 269 ms 73300 KB Output is correct
14 Correct 263 ms 74092 KB Output is correct
15 Correct 423 ms 134416 KB Output is correct
16 Correct 416 ms 135340 KB Output is correct
17 Correct 283 ms 76468 KB Output is correct
18 Correct 279 ms 76600 KB Output is correct
19 Correct 423 ms 138244 KB Output is correct
20 Correct 466 ms 138244 KB Output is correct