oj.uz

Submission #762465

# Submission time Handle Problem Language Result Execution time Memory
762465 2023-06-21T12:23:36 Z SanguineChameleon Game (IOI13_game) C++17
100 / 100
 2205 ms 52052 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

struct node_y {
	int lt = 0;
	int rt = 0;
	long long val = 0;
	int left = 0;
	int right = 0;

	void init(int _lt, int _rt) {
		lt = _lt;
		rt = _rt;
	}
};

const int max_nodes = 2e6 + 20;
int node_x_cnt = 0;
int node_y_cnt = 0;
int R, C;

node_y nodes_y[max_nodes];

struct node_x {
	int lt = 0;
	int rt = 0;
	int root_y = 0;
	int left = 0;
	int right = 0;

	void init(int _lt, int _rt) {
		lt = _lt;
		rt = _rt;
		root_y = ++node_y_cnt;
		nodes_y[root_y].init(0, (1 << 30) - 1);
	}
};

node_x nodes_x[max_nodes];

int root_x = ++node_x_cnt;

void init(int _R, int _C) {
	R = _R;
	C = _C;
	nodes_x[root_x].init(0, R - 1);
}

long long get_y(int cur, int ly, int ry) {
	if (!cur) {
		return 0LL;
	}
	if (nodes_y[cur].rt < ly || nodes_y[cur].lt > ry) {
		return 0LL;
	}
	if (ly <= nodes_y[cur].lt && nodes_y[cur].rt <= ry) {
		return nodes_y[cur].val;
	}
	return __gcd(get_y(nodes_y[cur].left, ly, ry), get_y(nodes_y[cur].right, ly, ry));
}

void update_y(int par, int cur, int y, long long val) {
	if (nodes_y[cur].lt == nodes_y[cur].rt) {
		if (nodes_x[par].lt == nodes_x[par].rt) {
			nodes_y[cur].val = val;
		}
		else {
			nodes_y[cur].val = __gcd(nodes_x[par].left ? get_y(nodes_x[nodes_x[par].left].root_y, y, y) : 0LL, nodes_x[par].right ? get_y(nodes_x[nodes_x[par].right].root_y, y, y) : 0LL);
		}
		return;
	}
	int mt = (nodes_y[cur].lt + nodes_y[cur].rt) / 2;
	if (y <= mt) {
		if (!nodes_y[cur].left) {
			nodes_y[cur].left = ++node_y_cnt;
			nodes_y[nodes_y[cur].left].init(y, y);
		}
		int lt = nodes_y[nodes_y[cur].left].lt;
		int rt = nodes_y[nodes_y[cur].left].rt;
		int prv = -1;
		while (y < lt || y > rt) {
			int len = (rt - lt + 1);
			if (lt & rt & len) {
				prv = 1;
				lt -= len;
			}
			else {
				prv = 0;
				rt += len;
			}
		}
		if (prv == 0) {
			int mid = ++node_y_cnt;
			nodes_y[mid].init(lt, rt);
			nodes_y[mid].left = nodes_y[cur].left;
			nodes_y[cur].left = mid;
		}
		if (prv == 1) {
			int mid = ++node_y_cnt;
			nodes_y[mid].init(lt, rt);
			nodes_y[mid].right = nodes_y[cur].left;
			nodes_y[cur].left = mid;
		}
		update_y(par, nodes_y[cur].left, y, val);
	}
	else {
		if (!nodes_y[cur].right) {
			nodes_y[cur].right = ++node_y_cnt;
			nodes_y[nodes_y[cur].right].init(y, y);
		}
		int lt = nodes_y[nodes_y[cur].right].lt;
		int rt = nodes_y[nodes_y[cur].right].rt;
		int prv = -1;
		while (y < lt || y > rt) {
			int len = (rt - lt + 1);
			if (lt & rt & len) {
				prv = 1;
				lt -= len;
			}
			else {
				prv = 0;
				rt += len;
			}
		}
		if (prv == 0) {
			int mid = ++node_y_cnt;
			nodes_y[mid].init(lt, rt);
			nodes_y[mid].left = nodes_y[cur].right;
			nodes_y[cur].right = mid;
		}
		if (prv == 1) {
			int mid = ++node_y_cnt;
			nodes_y[mid].init(lt, rt);
			nodes_y[mid].right = nodes_y[cur].right;
			nodes_y[cur].right = mid;
		}
		update_y(par, nodes_y[cur].right, y, val);
	}
	nodes_y[cur].val = __gcd(nodes_y[cur].left ? nodes_y[nodes_y[cur].left].val : 0LL, nodes_y[cur].right ? nodes_y[nodes_y[cur].right].val : 0LL);
}

void update_x(int cur, int x, int y, long long val) {
	if (nodes_x[cur].lt == nodes_x[cur].rt) {
		update_y(cur, nodes_x[cur].root_y, y, val);
		return;
	}
	int mt = (nodes_x[cur].lt + nodes_x[cur].rt) / 2;
	if (x <= mt) {
		if (!nodes_x[cur].left) {
			nodes_x[cur].left = ++node_x_cnt;
			nodes_x[nodes_x[cur].left].init(nodes_x[cur].lt, mt);
		}
		update_x(nodes_x[cur].left, x, y, val);
	}
	else {
		if (!nodes_x[cur].right) {
			nodes_x[cur].right = ++node_x_cnt;
			nodes_x[nodes_x[cur].right].init(mt + 1, nodes_x[cur].rt);
		}
		update_x(nodes_x[cur].right, x, y, val);
	}
	update_y(cur, nodes_x[cur].root_y, y, val);
}

void update(int x, int y, long long val) {
	update_x(root_x, x, y, val);
}

long long get_x(int cur, int lx, int rx, int ly, int ry) {
	if (!cur) {
		return 0LL;
	}
	if (nodes_x[cur].rt < lx || nodes_x[cur].lt > rx) {
		return 0LL;
	}
	if (lx <= nodes_x[cur].lt && nodes_x[cur].rt <= rx) {
		return get_y(nodes_x[cur].root_y, ly, ry);
	}
	return __gcd(get_x(nodes_x[cur].left, lx, rx, ly, ry), get_x(nodes_x[cur].right, lx, rx, ly, ry));
}

long long calculate(int lx, int ly, int rx, int ry) {
	return get_x(root_x, lx, rx, ly, ry);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 394 ms 7160 KB Output is correct
5 Correct 225 ms 7484 KB Output is correct
6 Correct 330 ms 4240 KB Output is correct
7 Correct 368 ms 3800 KB Output is correct
8 Correct 250 ms 3728 KB Output is correct
9 Correct 357 ms 4044 KB Output is correct
10 Correct 336 ms 3608 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 232 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 655 ms 8908 KB Output is correct
13 Correct 1186 ms 3804 KB Output is correct
14 Correct 185 ms 1740 KB Output is correct
15 Correct 1276 ms 4412 KB Output is correct
16 Correct 152 ms 6300 KB Output is correct
17 Correct 531 ms 4764 KB Output is correct
18 Correct 824 ms 6636 KB Output is correct
19 Correct 716 ms 6756 KB Output is correct
20 Correct 671 ms 6156 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 395 ms 7088 KB Output is correct
13 Correct 224 ms 7344 KB Output is correct
14 Correct 328 ms 4240 KB Output is correct
15 Correct 363 ms 3880 KB Output is correct
16 Correct 246 ms 3660 KB Output is correct
17 Correct 351 ms 3900 KB Output is correct
18 Correct 330 ms 3816 KB Output is correct
19 Correct 658 ms 9036 KB Output is correct
20 Correct 1181 ms 3980 KB Output is correct
21 Correct 183 ms 2024 KB Output is correct
22 Correct 1275 ms 4980 KB Output is correct
23 Correct 153 ms 6620 KB Output is correct
24 Correct 529 ms 5108 KB Output is correct
25 Correct 813 ms 6988 KB Output is correct
26 Correct 733 ms 6936 KB Output is correct
27 Correct 689 ms 6316 KB Output is correct
28 Correct 306 ms 21324 KB Output is correct
29 Correct 926 ms 23796 KB Output is correct
30 Correct 1728 ms 17848 KB Output is correct
31 Correct 1585 ms 14364 KB Output is correct
32 Correct 254 ms 2960 KB Output is correct
33 Correct 369 ms 3272 KB Output is correct
34 Correct 200 ms 20924 KB Output is correct
35 Correct 630 ms 12528 KB Output is correct
36 Correct 1190 ms 21132 KB Output is correct
37 Correct 964 ms 21172 KB Output is correct
38 Correct 919 ms 20376 KB Output is correct
39 Correct 777 ms 16824 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 308 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 391 ms 7952 KB Output is correct
13 Correct 225 ms 8124 KB Output is correct
14 Correct 327 ms 5032 KB Output is correct
15 Correct 371 ms 4616 KB Output is correct
16 Correct 247 ms 4452 KB Output is correct
17 Correct 356 ms 4684 KB Output is correct
18 Correct 325 ms 4416 KB Output is correct
19 Correct 654 ms 9548 KB Output is correct
20 Correct 1232 ms 4536 KB Output is correct
21 Correct 181 ms 2288 KB Output is correct
22 Correct 1331 ms 5208 KB Output is correct
23 Correct 154 ms 7116 KB Output is correct
24 Correct 528 ms 5580 KB Output is correct
25 Correct 821 ms 7556 KB Output is correct
26 Correct 727 ms 7632 KB Output is correct
27 Correct 670 ms 7116 KB Output is correct
28 Correct 298 ms 21448 KB Output is correct
29 Correct 916 ms 23076 KB Output is correct
30 Correct 1653 ms 17164 KB Output is correct
31 Correct 1521 ms 13680 KB Output is correct
32 Correct 251 ms 2304 KB Output is correct
33 Correct 340 ms 2896 KB Output is correct
34 Correct 223 ms 20000 KB Output is correct
35 Correct 628 ms 11648 KB Output is correct
36 Correct 1202 ms 20252 KB Output is correct
37 Correct 905 ms 20324 KB Output is correct
38 Correct 949 ms 19788 KB Output is correct
39 Correct 430 ms 50560 KB Output is correct
40 Correct 1559 ms 52052 KB Output is correct
41 Correct 2205 ms 40216 KB Output is correct
42 Correct 2017 ms 32148 KB Output is correct
43 Correct 345 ms 46808 KB Output is correct
44 Correct 309 ms 10572 KB Output is correct
45 Correct 762 ms 25320 KB Output is correct
46 Correct 1518 ms 51020 KB Output is correct
47 Correct 1526 ms 50944 KB Output is correct
48 Correct 1403 ms 50480 KB Output is correct
49 Correct 1 ms 312 KB Output is correct