oj.uz

Submission #729385

# Submission time Handle Problem Language Result Execution time Memory
729385 2023-04-24T02:12:24 Z kevlu8 Game (IOI13_game) C++17
100 / 100
 3003 ms 82228 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define boost() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n, m, q;

struct node1d {
	node1d(int v, int x, int y) : v(v), x(x), y(y), l(NULL), r(NULL) {}
	ll v;
	int x, y; // range
	node1d *l, *r;
};

struct node2d {
	node2d() : l(NULL), r(NULL), segtree(0, 1, m) {}
	node2d *l, *r;
	node1d segtree;
} *root;

void update1d(node1d *root, int i, ll v) {
	int s = root->x, e = root->y, mid = (s + e) >> 1;
	if (s == e) {
		root->v = v;
		return;
	}
	node1d **child = &(i <= mid ? root->l : root->r);
	if (*child == NULL) {
		*child = new node1d(v, i, i);
		(*child)->v = v;
	} else if ((*child)->x <= i && i <= (*child)->y) {
		update1d(*child, i, v);
	} else {
		do {
			if (i <= mid) e = mid;
			else s = mid + 1;
			mid = (s + e) >> 1;
		} while ((i <= mid) == ((*child)->y <= mid));
		node1d *node2 = new node1d(0, s, e);
		if ((*child)->y <= mid) node2->l = *child;
		else node2->r = *child;
		*child = node2;
		update1d(*child, i, v);
	}
	root->v = __gcd(root->l ? root->l->v : 0, root->r ? root->r->v : 0);
}

ll calculate1d(node1d *root, int l, int r) {
	if (root == NULL || root->x > r || root->y < l) return 0;
	if (l <= root->x && root->y <= r) {
		return root->v;
	}
	return __gcd(calculate1d(root->l, l, r), calculate1d(root->r, l, r));
}

void update2d(node2d *root, int l, int r, int x, int y, ll v) {
	if (l == r) {
		update1d(&root->segtree, y, v);
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) {
		if (root->l == NULL) root->l = new node2d();
		update2d(root->l, l, mid, x, y, v);
	} else {
		if (root->r == NULL) root->r = new node2d();
		update2d(root->r, mid+1, r, x, y, v);
	}
	ll value = __gcd(root->l ? calculate1d(&root->l->segtree, y, y) : 0, root->r ? calculate1d(&root->r->segtree, y, y) : 0);
	update1d(&root->segtree, y, value);
}

ll calculate2d(node2d *root, int l, int r, int x, int y, int x2, int y2) {
	if (root == NULL || l > x2 || r < x) return 0; 
	if (x <= l && r <= x2) return calculate1d(&root->segtree, y, y2);
	int mid = (l + r) >> 1;
	return __gcd(calculate2d(root->l, l, mid, x, y, x2, y2), calculate2d(root->r, mid+1, r, x, y, x2, y2));
}

void init(int n, int m) {
	::n = n;
	::m = m;
	root = new node2d();
}

void update(int x, int y, ll v) {
	++x, ++y;
	update2d(root, 1, n, x, y, v);
}

ll calculate(int x, int y, int x2, int y2) {
	++x, ++y, ++x2, ++y2;
	return calculate2d(root, 1, n, x, y, x2, y2);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 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 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 340 KB Output is correct
12 Correct 0 ms 300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 264 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 471 ms 12712 KB Output is correct
5 Correct 366 ms 12536 KB Output is correct
6 Correct 380 ms 10016 KB Output is correct
7 Correct 469 ms 9784 KB Output is correct
8 Correct 326 ms 8076 KB Output is correct
9 Correct 514 ms 9792 KB Output is correct
10 Correct 478 ms 9488 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 236 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 788 ms 15520 KB Output is correct
13 Correct 1443 ms 8784 KB Output is correct
14 Correct 231 ms 5592 KB Output is correct
15 Correct 1570 ms 10600 KB Output is correct
16 Correct 189 ms 14012 KB Output is correct
17 Correct 594 ms 11180 KB Output is correct
18 Correct 1161 ms 15524 KB Output is correct
19 Correct 923 ms 15732 KB Output is correct
20 Correct 876 ms 15020 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 481 ms 12796 KB Output is correct
13 Correct 305 ms 12636 KB Output is correct
14 Correct 381 ms 10036 KB Output is correct
15 Correct 465 ms 9780 KB Output is correct
16 Correct 341 ms 7996 KB Output is correct
17 Correct 448 ms 9784 KB Output is correct
18 Correct 381 ms 9500 KB Output is correct
19 Correct 750 ms 15560 KB Output is correct
20 Correct 1378 ms 8940 KB Output is correct
21 Correct 220 ms 5580 KB Output is correct
22 Correct 1573 ms 10480 KB Output is correct
23 Correct 180 ms 14020 KB Output is correct
24 Correct 656 ms 11068 KB Output is correct
25 Correct 1273 ms 15540 KB Output is correct
26 Correct 881 ms 15668 KB Output is correct
27 Correct 888 ms 15080 KB Output is correct
28 Correct 387 ms 43180 KB Output is correct
29 Correct 1107 ms 45312 KB Output is correct
30 Correct 2137 ms 35296 KB Output is correct
31 Correct 1967 ms 28472 KB Output is correct
32 Correct 336 ms 10188 KB Output is correct
33 Correct 477 ms 10676 KB Output is correct
34 Correct 264 ms 39148 KB Output is correct
35 Correct 863 ms 26964 KB Output is correct
36 Correct 1680 ms 43284 KB Output is correct
37 Correct 1322 ms 43344 KB Output is correct
38 Correct 1361 ms 42892 KB Output is correct
39 Correct 1263 ms 35720 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 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 304 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 448 ms 12716 KB Output is correct
13 Correct 318 ms 12540 KB Output is correct
14 Correct 409 ms 10020 KB Output is correct
15 Correct 536 ms 9804 KB Output is correct
16 Correct 286 ms 8208 KB Output is correct
17 Correct 504 ms 9840 KB Output is correct
18 Correct 446 ms 9552 KB Output is correct
19 Correct 718 ms 15504 KB Output is correct
20 Correct 1337 ms 8812 KB Output is correct
21 Correct 220 ms 5580 KB Output is correct
22 Correct 1510 ms 10572 KB Output is correct
23 Correct 182 ms 14036 KB Output is correct
24 Correct 639 ms 11020 KB Output is correct
25 Correct 1279 ms 15536 KB Output is correct
26 Correct 1020 ms 15784 KB Output is correct
27 Correct 929 ms 14988 KB Output is correct
28 Correct 486 ms 43204 KB Output is correct
29 Correct 1129 ms 45360 KB Output is correct
30 Correct 2114 ms 35196 KB Output is correct
31 Correct 1905 ms 28536 KB Output is correct
32 Correct 342 ms 10232 KB Output is correct
33 Correct 432 ms 10660 KB Output is correct
34 Correct 254 ms 39128 KB Output is correct
35 Correct 823 ms 26960 KB Output is correct
36 Correct 2024 ms 43280 KB Output is correct
37 Correct 1598 ms 43456 KB Output is correct
38 Correct 1457 ms 42816 KB Output is correct
39 Correct 549 ms 81088 KB Output is correct
40 Correct 1920 ms 82228 KB Output is correct
41 Correct 3003 ms 67276 KB Output is correct
42 Correct 2719 ms 52388 KB Output is correct
43 Correct 494 ms 76784 KB Output is correct
44 Correct 422 ms 10720 KB Output is correct
45 Correct 1078 ms 35676 KB Output is correct
46 Correct 2387 ms 81004 KB Output is correct
47 Correct 2161 ms 80916 KB Output is correct
48 Correct 2364 ms 80608 KB Output is correct
49 Correct 1 ms 212 KB Output is correct