# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
379563 |
2021-03-18T15:49:47 Z |
WLZ |
Game (IOI13_game) |
C++14 |
|
5103 ms |
101100 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int r, c;
long long gcd(long long a, long long b) {
while (b > 0) {
swap(a, b);
b %= a;
}
return a;
}
struct node {
int l, r, idx;
long long val;
node *left, *right;
node(int _l, int _r) : l(_l), r(_r), idx(-1), val(-1), left(nullptr), right(nullptr) {}
};
void update(node *cur, int idx, long long val);
void propagate(node *cur, int idx, long long val) {
if (idx <= (cur->l + cur->r) / 2) {
if (cur->left == nullptr) cur->left = new node(cur->l, (cur->l + cur->r) / 2);
update(cur->left, idx, val);
} else {
if (cur->right == nullptr) cur->right = new node((cur->l + cur->r) / 2 + 1, cur->r);
update(cur->right, idx, val);
}
}
void update(node *cur, int idx, long long val) {
if (cur->l == cur->r) {
cur->val = val;
return;
}
if (cur->idx == idx) cur->val = val;
else if (cur->idx != -1) {
propagate(cur, cur->idx, cur->val);
cur->idx = -1;
} else if (cur->val == -1) {
cur->idx = idx, cur->val = val;
return;
}
propagate(cur, idx, val);
cur->val = gcd(cur->left == nullptr ? 0 : cur->left->val, cur->right == nullptr ? 0 : cur->right->val);
}
long long query(node *cur, int l, int r) {
if (l <= cur->l && cur->r <= r) return cur->val;
if (l > cur->r || r < cur->l) return 0;
if (cur->idx != -1) return (l <= cur->idx && cur->idx <= r) ? cur->val : 0;
long long ans = 0;
if (cur->left != nullptr) ans = gcd(ans, query(cur->left, l, r));
if (cur->right != nullptr) ans = gcd(ans, query(cur->right, l, r));
return ans;
}
struct node2D {
int l, r;
node *root;
node2D *left, *right;
node2D(int _l, int _r) : l(_l), r(_r), root(nullptr), left(nullptr), right(nullptr) {}
} *root;
void update2D(node2D *cur, int x, int y, long long val) {
if (cur->root == nullptr) cur->root = new node(0, c - 1);
if (cur->l == cur->r) {
update(cur->root, y, val);
return;
}
if (x <= (cur->l + cur->r) / 2) {
if (cur->left == nullptr) cur->left = new node2D(cur->l, (cur->l + cur->r) / 2);
update2D(cur->left, x, y, val);
} else {
if (cur->right == nullptr) cur->right = new node2D((cur->l + cur->r) / 2 + 1, cur->r);
update2D(cur->right, x, y, val);
}
update(cur->root, y, gcd(cur->left == nullptr ? 0 : query(cur->left->root, y, y), cur->right == nullptr ? 0 : query(cur->right->root, y, y)));
}
long long query2D(node2D *cur, int x1, int y1, int x2, int y2) {
if (cur->l > x2 || cur->r < x1) return 0;
if (x1 <= cur->l && cur->r <= x2) return cur->root == nullptr ? 0 : query(cur->root, y1, y2);
long long ans = 0;
if (cur->left != nullptr) ans = gcd(ans, query2D(cur->left, x1, y1, x2, y2));
if (cur->right != nullptr) ans = gcd(ans, query2D(cur->right, x1, y1, x2, y2));
return ans;
}
void init(int R, int C) {
r = R, c = C;
root = new node2D(0, r - 1);
}
void update(int P, int Q, long long K) {
update2D(root, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return query2D(root, P, Q, U, V);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
611 ms |
13708 KB |
Output is correct |
5 |
Correct |
404 ms |
13548 KB |
Output is correct |
6 |
Correct |
500 ms |
11288 KB |
Output is correct |
7 |
Correct |
597 ms |
10860 KB |
Output is correct |
8 |
Correct |
367 ms |
8556 KB |
Output is correct |
9 |
Correct |
564 ms |
10732 KB |
Output is correct |
10 |
Correct |
524 ms |
10476 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1002 ms |
17132 KB |
Output is correct |
13 |
Correct |
1639 ms |
10612 KB |
Output is correct |
14 |
Correct |
315 ms |
5740 KB |
Output is correct |
15 |
Correct |
1921 ms |
12884 KB |
Output is correct |
16 |
Correct |
230 ms |
15724 KB |
Output is correct |
17 |
Correct |
822 ms |
12196 KB |
Output is correct |
18 |
Correct |
1625 ms |
17364 KB |
Output is correct |
19 |
Correct |
1366 ms |
17532 KB |
Output is correct |
20 |
Correct |
1242 ms |
17024 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
667 ms |
13804 KB |
Output is correct |
13 |
Correct |
405 ms |
13340 KB |
Output is correct |
14 |
Correct |
515 ms |
11240 KB |
Output is correct |
15 |
Correct |
570 ms |
10604 KB |
Output is correct |
16 |
Correct |
372 ms |
8556 KB |
Output is correct |
17 |
Correct |
557 ms |
11060 KB |
Output is correct |
18 |
Correct |
513 ms |
10604 KB |
Output is correct |
19 |
Correct |
1030 ms |
16936 KB |
Output is correct |
20 |
Correct |
1670 ms |
10336 KB |
Output is correct |
21 |
Correct |
312 ms |
5996 KB |
Output is correct |
22 |
Correct |
1947 ms |
12860 KB |
Output is correct |
23 |
Correct |
237 ms |
15980 KB |
Output is correct |
24 |
Correct |
836 ms |
12112 KB |
Output is correct |
25 |
Correct |
1722 ms |
17356 KB |
Output is correct |
26 |
Correct |
1285 ms |
17516 KB |
Output is correct |
27 |
Correct |
1243 ms |
17080 KB |
Output is correct |
28 |
Correct |
638 ms |
51180 KB |
Output is correct |
29 |
Correct |
1622 ms |
46324 KB |
Output is correct |
30 |
Correct |
3894 ms |
45292 KB |
Output is correct |
31 |
Correct |
3593 ms |
39468 KB |
Output is correct |
32 |
Correct |
608 ms |
10860 KB |
Output is correct |
33 |
Correct |
858 ms |
14640 KB |
Output is correct |
34 |
Correct |
300 ms |
39916 KB |
Output is correct |
35 |
Correct |
1118 ms |
27372 KB |
Output is correct |
36 |
Correct |
2356 ms |
44100 KB |
Output is correct |
37 |
Correct |
1834 ms |
44388 KB |
Output is correct |
38 |
Correct |
1861 ms |
43928 KB |
Output is correct |
39 |
Correct |
1492 ms |
36460 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
641 ms |
13676 KB |
Output is correct |
13 |
Correct |
410 ms |
13580 KB |
Output is correct |
14 |
Correct |
504 ms |
10988 KB |
Output is correct |
15 |
Correct |
569 ms |
10732 KB |
Output is correct |
16 |
Correct |
366 ms |
8684 KB |
Output is correct |
17 |
Correct |
582 ms |
10860 KB |
Output is correct |
18 |
Correct |
522 ms |
10348 KB |
Output is correct |
19 |
Correct |
991 ms |
16876 KB |
Output is correct |
20 |
Correct |
1644 ms |
10456 KB |
Output is correct |
21 |
Correct |
348 ms |
5744 KB |
Output is correct |
22 |
Correct |
1902 ms |
12908 KB |
Output is correct |
23 |
Correct |
235 ms |
15724 KB |
Output is correct |
24 |
Correct |
775 ms |
12012 KB |
Output is correct |
25 |
Correct |
1595 ms |
17260 KB |
Output is correct |
26 |
Correct |
1281 ms |
17516 KB |
Output is correct |
27 |
Correct |
1208 ms |
17004 KB |
Output is correct |
28 |
Correct |
626 ms |
51180 KB |
Output is correct |
29 |
Correct |
1584 ms |
46444 KB |
Output is correct |
30 |
Correct |
3829 ms |
45524 KB |
Output is correct |
31 |
Correct |
3581 ms |
39172 KB |
Output is correct |
32 |
Correct |
596 ms |
10732 KB |
Output is correct |
33 |
Correct |
837 ms |
14572 KB |
Output is correct |
34 |
Correct |
312 ms |
40044 KB |
Output is correct |
35 |
Correct |
1088 ms |
27244 KB |
Output is correct |
36 |
Correct |
2338 ms |
44216 KB |
Output is correct |
37 |
Correct |
1829 ms |
44292 KB |
Output is correct |
38 |
Correct |
1766 ms |
43992 KB |
Output is correct |
39 |
Correct |
869 ms |
101100 KB |
Output is correct |
40 |
Correct |
2659 ms |
84908 KB |
Output is correct |
41 |
Correct |
5103 ms |
89676 KB |
Output is correct |
42 |
Correct |
4675 ms |
75980 KB |
Output is correct |
43 |
Correct |
552 ms |
79596 KB |
Output is correct |
44 |
Correct |
849 ms |
11244 KB |
Output is correct |
45 |
Correct |
1447 ms |
36264 KB |
Output is correct |
46 |
Correct |
2953 ms |
83744 KB |
Output is correct |
47 |
Correct |
2996 ms |
83692 KB |
Output is correct |
48 |
Correct |
2834 ms |
83320 KB |
Output is correct |
49 |
Correct |
1 ms |
364 KB |
Output is correct |