oj.uz

Submission #545996

# Submission time Handle Problem Language Result Execution time Memory
545996 2022-04-05T21:42:56 Z sliviu Game (IOI13_game) C++17
100 / 100
 2680 ms 77156 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

static int R, C;

ll gcd2(ll x, ll y) {
	if (y == 0) return x;
	return gcd2(y, x % y);
}

struct nodex {
	nodex* left = 0, * right = 0;
	int l, r;
	ll val;
	nodex(int _l, int _r) :l(_l), r(_r) {}
};

struct nodey {
	nodey* left = 0, * right = 0;
	nodex* val = new nodex(1, C);;
} *root;

void UpdateX(int pos, ll val, nodex* nod) {
	int l = nod->l, r = nod->r, m = (l + r) / 2;
	if (l == r) {
		nod->val = val;
		return;
	}
	nodex*& son = pos <= m ? nod->left : nod->right;
	if (!son) {
		son = new nodex(pos, pos);
		son->val = val;
	}
	else if (son->l <= pos && pos <= son->r)
		UpdateX(pos, val, son);
	else {
		do {
			if (pos <= m)
				r = m;
			else
				l = m + 1;
			m = (l + r) / 2;
		} while (pos <= m == son->r <= m);
		nodex* nn = new nodex(l, r);
		if (son->r <= m)
			nn->left = son;
		else
			nn->right = son;
		son = nn;
		UpdateX(pos, val, son);
	}
	nod->val = gcd2(nod->left ? nod->left->val : 0, nod->right ? nod->right->val : 0);
}

ll QueryX(int posleft, int posright, nodex* node) {
	if (!node)
		return 0;
	if (posleft <= node->l && node->r <= posright)
		return node->val;
	ll ans = 0;
	int m = (node->l + node->r) / 2;
	if (posleft <= m)
		ans = gcd2(ans, QueryX(posleft, posright, node->left));
	if (posright > m)
		ans = gcd2(ans, QueryX(posleft, posright, node->right));
	return ans;
}

void UpdateY(int posy, int posx, ll val, nodey* node = root, int left = 1, int right = R) {
	if (left == right) {
		UpdateX(posx, val, node->val);
		return;
	}
	int m = (left + right) / 2;
	if (posy <= m) {
		if (!node->left)
			node->left = new nodey();
		UpdateY(posy, posx, val, node->left, left, m);
	}
	else {
		if (!node->right)
			node->right = new nodey();
		UpdateY(posy, posx, val, node->right, m + 1, right);
	}
	UpdateX(posx, gcd2(node->left ? QueryX(posx, posx, node->left->val) : 0, node->right ? QueryX(posx, posx, node->right->val) : 0), node->val);
}

ll QueryY(int poslefty, int posrighty, int posleftx, int posrightx, nodey* node = root, int left = 1, int right = R) {
	if (!node)
		return 0;
	if (poslefty <= left && right <= posrighty)
		return QueryX(posleftx, posrightx, node->val);
	ll ans = 0;
	int m = (left + right) / 2;
	if (poslefty <= m)
		ans = gcd2(ans, QueryY(poslefty, posrighty, posleftx, posrightx, node->left, left, m));
	if (posrighty > m)
		ans = gcd2(ans, QueryY(poslefty, posrighty, posleftx, posrightx, node->right, m + 1, right));
	return ans;
}

void init(int r, int c) {
	R = r, C = c;
	root = new nodey();
}

void update(int p, int q, ll k) {
	++p, ++q;
	UpdateY(p, q, k);
}

ll calculate(int p, int q, int u, int v) {
	++p, ++q, ++u, ++v;
	return QueryY(p, u, q, v);
}

Compilation message

game.cpp: In function 'void UpdateX(int, ll, nodex*)':
game.cpp:46:16: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   46 |   } while (pos <= m == son->r <= m);
      |            ~~~~^~~~

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 340 KB Output is correct
3 Correct 1 ms 340 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 0 ms 340 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 0 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 420 ms 8252 KB Output is correct
5 Correct 308 ms 8640 KB Output is correct
6 Correct 351 ms 5312 KB Output is correct
7 Correct 396 ms 5104 KB Output is correct
8 Correct 255 ms 3868 KB Output is correct
9 Correct 398 ms 5188 KB Output is correct
10 Correct 399 ms 4792 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 0 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 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 0 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 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 677 ms 11480 KB Output is correct
13 Correct 1227 ms 5044 KB Output is correct
14 Correct 212 ms 828 KB Output is correct
15 Correct 1354 ms 6296 KB Output is correct
16 Correct 167 ms 9932 KB Output is correct
17 Correct 531 ms 6216 KB Output is correct
18 Correct 958 ms 10308 KB Output is correct
19 Correct 784 ms 10380 KB Output is correct
20 Correct 730 ms 9884 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 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 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 0 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 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 427 ms 8348 KB Output is correct
13 Correct 319 ms 8572 KB Output is correct
14 Correct 354 ms 5328 KB Output is correct
15 Correct 401 ms 5132 KB Output is correct
16 Correct 261 ms 3792 KB Output is correct
17 Correct 384 ms 5432 KB Output is correct
18 Correct 352 ms 4952 KB Output is correct
19 Correct 682 ms 11516 KB Output is correct
20 Correct 1201 ms 4944 KB Output is correct
21 Correct 204 ms 920 KB Output is correct
22 Correct 1346 ms 6160 KB Output is correct
23 Correct 178 ms 10016 KB Output is correct
24 Correct 547 ms 6220 KB Output is correct
25 Correct 985 ms 10300 KB Output is correct
26 Correct 799 ms 10400 KB Output is correct
27 Correct 724 ms 9796 KB Output is correct
28 Correct 402 ms 35348 KB Output is correct
29 Correct 1024 ms 38140 KB Output is correct
30 Correct 1940 ms 29744 KB Output is correct
31 Correct 1758 ms 22808 KB Output is correct
32 Correct 306 ms 968 KB Output is correct
33 Correct 414 ms 1760 KB Output is correct
34 Correct 231 ms 35188 KB Output is correct
35 Correct 701 ms 18668 KB Output is correct
36 Correct 1486 ms 35388 KB Output is correct
37 Correct 1132 ms 35876 KB Output is correct
38 Correct 1116 ms 34992 KB Output is correct
39 Correct 960 ms 27528 KB Output is correct
40 Correct 0 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 0 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 0 ms 340 KB Output is correct
12 Correct 416 ms 8248 KB Output is correct
13 Correct 327 ms 8596 KB Output is correct
14 Correct 360 ms 5324 KB Output is correct
15 Correct 396 ms 5112 KB Output is correct
16 Correct 260 ms 3808 KB Output is correct
17 Correct 387 ms 5300 KB Output is correct
18 Correct 343 ms 4844 KB Output is correct
19 Correct 679 ms 11500 KB Output is correct
20 Correct 1202 ms 4920 KB Output is correct
21 Correct 210 ms 924 KB Output is correct
22 Correct 1354 ms 6100 KB Output is correct
23 Correct 189 ms 9932 KB Output is correct
24 Correct 575 ms 6188 KB Output is correct
25 Correct 1177 ms 10448 KB Output is correct
26 Correct 931 ms 10492 KB Output is correct
27 Correct 693 ms 9912 KB Output is correct
28 Correct 452 ms 35404 KB Output is correct
29 Correct 1027 ms 38276 KB Output is correct
30 Correct 1957 ms 29824 KB Output is correct
31 Correct 1759 ms 22848 KB Output is correct
32 Correct 307 ms 944 KB Output is correct
33 Correct 394 ms 1536 KB Output is correct
34 Correct 233 ms 35056 KB Output is correct
35 Correct 702 ms 18724 KB Output is correct
36 Correct 1492 ms 35636 KB Output is correct
37 Correct 1163 ms 35860 KB Output is correct
38 Correct 1119 ms 34948 KB Output is correct
39 Correct 554 ms 76236 KB Output is correct
40 Correct 1656 ms 77156 KB Output is correct
41 Correct 2680 ms 63004 KB Output is correct
42 Correct 2510 ms 47492 KB Output is correct
43 Correct 436 ms 75328 KB Output is correct
44 Correct 370 ms 1104 KB Output is correct
45 Correct 994 ms 27588 KB Output is correct
46 Correct 2091 ms 75700 KB Output is correct
47 Correct 2041 ms 75660 KB Output is correct
48 Correct 1937 ms 75172 KB Output is correct
49 Correct 0 ms 212 KB Output is correct