#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd(ll x, ll y) { return !y ? x : gcd(y, x % y); }
int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct TreapNode {
TreapNode *l, *r;
int pos, key, mn, mx;
ll val, g;
TreapNode(int position, ll value) {
l = r = nullptr;
mn = mx = pos = position;
key = rng();
val = g = value;
}
void update() {
g = val;
if (l) g = gcd(g, l->g);
if (r) g = gcd(g, r->g);
mn = (l ? l->mn : pos);
mx = (r ? r->mx : pos);
}
};
struct Treap {
TreapNode *root;
Treap() {
root = nullptr;
srand(rnd());
}
void split(TreapNode *t, int pos, TreapNode *&l, TreapNode *&r) {
if (t == nullptr) {
l = r = nullptr;
return;
}
if (t->pos < pos) {
split(t->r, pos, l, r);
t->r = l;
l = t;
} else {
split(t->l, pos, l, r);
t->l = r;
r = t;
}
t->update();
}
TreapNode* merge(TreapNode *l, TreapNode *r) {
if (!l || !r) return l ? l : r;
if (l->key < r->key) {
l->r = merge(l->r, r);
l->update();
return l;
} else {
r->l = merge(l, r->l);
r->update();
return r;
}
}
bool find(int pos) {
TreapNode *t = root;
while (t) {
if (t->pos == pos) return true;
if (t->pos > pos) t = t->l;
else t = t->r;
}
return false;
}
void update(TreapNode *t, int pos, ll val) {
if (t->pos == pos) {
t->val = val;
t->update();
return;
}
if (t->pos > pos) update(t->l, pos, val);
else update(t->r, pos, val);
t->update();
}
void insert(int pos, ll val) {
if (find(pos)) update(root, pos, val);
else {
TreapNode *l, *r;
split(root, pos, l, r);
root = merge(merge(l, new TreapNode(pos, val)), r);
}
}
ll query(TreapNode *t, int st, int en) {
if (t->mx < st || en < t->mn) return 0;
if (st <= t->mn && t->mx <= en) return t->g;
ll ans = (st <= t->pos && t->pos <= en ? t->val : 0);
if (t->l) ans = gcd(ans, query(t->l, st, en));
if (t->r) ans = gcd(ans, query(t->r, st, en));
return ans;
}
ll query(int st, int en) {
if (!root) return 0;
return query(root, st, en);
}
};
struct Segtree {
Segtree *l, *r;
Treap treap;
int lo, hi;
Segtree() { l = r = nullptr; }
Segtree(int st, int en) {
l = r = nullptr;
lo = st, hi = en;
}
void new_left() {
if (!l) l = new Segtree(lo, (lo + hi) / 2);
}
void new_right() {
if (!r) r = new Segtree((lo + hi) / 2 + 1, hi);
}
void fix(int pos) {
ll val = 0;
if (l) val = gcd(val, l->treap.query(pos, pos));
if (r) val = gcd(val, r->treap.query(pos, pos));
treap.insert(pos, val);
}
void update(int x, int y, ll val) {
if (hi < x || x < lo) return;
if (lo == hi) {
treap.insert(y, val);
return;
}
if (x <= (lo + hi) / 2) {
new_left();
l->update(x, y, val);
} else {
new_right();
r->update(x, y, val);
}
fix(y);
}
ll query(int t, int b, int st, int en) {
if (hi < t || b < lo) return 0;
if (t <= lo && hi <= b) return treap.query(st, en);
ll ans = 0;
if (l) ans = gcd(ans, l->query(t, b, st, en));
if (r) ans = gcd(ans, r->query(t, b, st, en));
return ans;
}
};
Segtree segtree;
void init(int R, int C) {
srand(12341234);
segtree = Segtree(0, R - 1);
}
void update(int P, int Q, ll K) { segtree.update(P, Q, K); }
ll calculate(int P, int Q, int U, int V) {
return segtree.query(P, U, Q, V);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
308 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
308 KB |
Output is correct |
9 |
Correct |
2 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
503 ms |
11380 KB |
Output is correct |
5 |
Correct |
253 ms |
11176 KB |
Output is correct |
6 |
Correct |
600 ms |
8636 KB |
Output is correct |
7 |
Correct |
623 ms |
8428 KB |
Output is correct |
8 |
Correct |
361 ms |
7388 KB |
Output is correct |
9 |
Correct |
543 ms |
8544 KB |
Output is correct |
10 |
Correct |
524 ms |
8136 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
436 KB |
Output is correct |
4 |
Correct |
1 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 |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
667 ms |
13308 KB |
Output is correct |
13 |
Correct |
1051 ms |
7744 KB |
Output is correct |
14 |
Correct |
218 ms |
5596 KB |
Output is correct |
15 |
Correct |
1169 ms |
8992 KB |
Output is correct |
16 |
Correct |
253 ms |
11468 KB |
Output is correct |
17 |
Correct |
716 ms |
9664 KB |
Output is correct |
18 |
Correct |
1352 ms |
12968 KB |
Output is correct |
19 |
Correct |
1076 ms |
13028 KB |
Output is correct |
20 |
Correct |
985 ms |
12396 KB |
Output is correct |
21 |
Correct |
1 ms |
260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
304 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 |
477 ms |
11424 KB |
Output is correct |
13 |
Correct |
241 ms |
11236 KB |
Output is correct |
14 |
Correct |
503 ms |
8668 KB |
Output is correct |
15 |
Correct |
572 ms |
8412 KB |
Output is correct |
16 |
Correct |
337 ms |
7372 KB |
Output is correct |
17 |
Correct |
543 ms |
8464 KB |
Output is correct |
18 |
Correct |
497 ms |
8132 KB |
Output is correct |
19 |
Correct |
650 ms |
13380 KB |
Output is correct |
20 |
Correct |
1096 ms |
7692 KB |
Output is correct |
21 |
Correct |
206 ms |
5580 KB |
Output is correct |
22 |
Correct |
1096 ms |
9024 KB |
Output is correct |
23 |
Correct |
243 ms |
11332 KB |
Output is correct |
24 |
Correct |
706 ms |
9656 KB |
Output is correct |
25 |
Correct |
1214 ms |
12916 KB |
Output is correct |
26 |
Correct |
1032 ms |
13072 KB |
Output is correct |
27 |
Correct |
978 ms |
12340 KB |
Output is correct |
28 |
Correct |
701 ms |
39000 KB |
Output is correct |
29 |
Correct |
1373 ms |
41636 KB |
Output is correct |
30 |
Correct |
1535 ms |
29868 KB |
Output is correct |
31 |
Correct |
1395 ms |
24648 KB |
Output is correct |
32 |
Correct |
296 ms |
10208 KB |
Output is correct |
33 |
Correct |
422 ms |
10552 KB |
Output is correct |
34 |
Correct |
629 ms |
35532 KB |
Output is correct |
35 |
Correct |
1057 ms |
25452 KB |
Output is correct |
36 |
Correct |
2069 ms |
39740 KB |
Output is correct |
37 |
Correct |
1779 ms |
39812 KB |
Output is correct |
38 |
Correct |
1755 ms |
39244 KB |
Output is correct |
39 |
Correct |
1422 ms |
33068 KB |
Output is correct |
40 |
Correct |
1 ms |
304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
304 KB |
Output is correct |
5 |
Correct |
1 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 |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
501 ms |
11480 KB |
Output is correct |
13 |
Correct |
240 ms |
11212 KB |
Output is correct |
14 |
Correct |
498 ms |
8748 KB |
Output is correct |
15 |
Correct |
569 ms |
8340 KB |
Output is correct |
16 |
Correct |
344 ms |
7524 KB |
Output is correct |
17 |
Correct |
533 ms |
8512 KB |
Output is correct |
18 |
Correct |
519 ms |
8088 KB |
Output is correct |
19 |
Correct |
654 ms |
13268 KB |
Output is correct |
20 |
Correct |
1077 ms |
7724 KB |
Output is correct |
21 |
Correct |
210 ms |
5624 KB |
Output is correct |
22 |
Correct |
1151 ms |
9088 KB |
Output is correct |
23 |
Correct |
255 ms |
11488 KB |
Output is correct |
24 |
Correct |
704 ms |
9724 KB |
Output is correct |
25 |
Correct |
1223 ms |
13036 KB |
Output is correct |
26 |
Correct |
1026 ms |
13048 KB |
Output is correct |
27 |
Correct |
1010 ms |
12424 KB |
Output is correct |
28 |
Correct |
707 ms |
39004 KB |
Output is correct |
29 |
Correct |
1455 ms |
41856 KB |
Output is correct |
30 |
Correct |
1547 ms |
29828 KB |
Output is correct |
31 |
Correct |
1352 ms |
24576 KB |
Output is correct |
32 |
Correct |
286 ms |
10276 KB |
Output is correct |
33 |
Correct |
408 ms |
10484 KB |
Output is correct |
34 |
Correct |
640 ms |
35668 KB |
Output is correct |
35 |
Correct |
1053 ms |
25344 KB |
Output is correct |
36 |
Correct |
2183 ms |
39688 KB |
Output is correct |
37 |
Correct |
1788 ms |
40092 KB |
Output is correct |
38 |
Correct |
1757 ms |
39300 KB |
Output is correct |
39 |
Correct |
1197 ms |
71260 KB |
Output is correct |
40 |
Correct |
2626 ms |
73376 KB |
Output is correct |
41 |
Correct |
2514 ms |
55476 KB |
Output is correct |
42 |
Correct |
2165 ms |
43824 KB |
Output is correct |
43 |
Correct |
1341 ms |
68092 KB |
Output is correct |
44 |
Correct |
396 ms |
10792 KB |
Output is correct |
45 |
Correct |
1428 ms |
32992 KB |
Output is correct |
46 |
Correct |
3377 ms |
72240 KB |
Output is correct |
47 |
Correct |
3328 ms |
72332 KB |
Output is correct |
48 |
Correct |
3243 ms |
71816 KB |
Output is correct |
49 |
Correct |
1 ms |
216 KB |
Output is correct |