#include "bits/stdc++.h"
#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using K = array<int, 2>;
struct Node {
Node *l = 0, *r = 0;
ll v, g;
K key;
int y;
Node(ll val, K key) : v(val), g(val), key(key), y(rng()) {}
void pull();
};
ll val(Node* n) { return n ? n->g : 0; }
void Node::pull() { g = gcd(val(l), gcd(v, val(r))); }
pair<Node*, Node*> split(Node* n, K k) {
if (!n) return {};
if (n->key >= k) {
auto pa = split(n->l, k);
n->l = pa.second;
n->pull();
return {pa.first, n};
} else {
auto pa = split(n->r, k);
n->r = pa.first;
n->pull();
return {n, pa.second};
}
}
Node* merge(Node* l, Node* r) {
if (!l) return r;
if (!r) return l;
if (l->y > r->y) {
l->r = merge(l->r, r);
l->pull();
return l;
} else {
r->l = merge(l, r->l);
r->pull();
return r;
}
}
struct gcd_treap {
Node* root;
gcd_treap() : root{nullptr} {}
void set(K k, ll val) {
Node *L, *X, *R;
tie(L, X) = split(root, k);
++k[1];
tie(X, R) = split(X, k);
--k[1];
delete X;
auto new_node = new Node(val, k);
root = merge(L, merge(new_node, R));
}
ll query(int l, int r) {
const K kl = {l, -1}, kr = {r, -1};
Node *L, *X, *R;
tie(L, X) = split(root, kl);
tie(X, R) = split(X, kr);
const auto g = val(X);
root = merge(L, merge(X, R));
return g;
}
};
struct segtree {
int sz;
vector<gcd_treap> t;
segtree() {}
segtree(int n) : sz{1} {
while (sz < n) sz *= 2;
t.resize(2 * sz);
}
ll query(int l, int r, int u, int d) {
ll g = 0;
for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
if (l & 1) g = gcd(g, t[l++].query(u, d));
if (r & 1) g = gcd(g, t[--r].query(u, d));
}
return g;
}
void set(int x, int y, ll val) {
for (int p = x + sz; p > 0; p /= 2)
t[p].set({y, x}, val);
}
};
segtree t;
void init(int n, int m) { t = segtree(n); }
void update(int i, int j, ll val) {
t.set(i, j, val);
}
ll calculate(int l, int u, int r, int d) {
++r, ++d;
return t.query(l, r, u, d);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
586 ms |
7456 KB |
Output is correct |
5 |
Correct |
266 ms |
11584 KB |
Output is correct |
6 |
Correct |
968 ms |
9420 KB |
Output is correct |
7 |
Correct |
1074 ms |
8936 KB |
Output is correct |
8 |
Correct |
741 ms |
7548 KB |
Output is correct |
9 |
Correct |
1058 ms |
8864 KB |
Output is correct |
10 |
Correct |
948 ms |
8852 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1024 ms |
11328 KB |
Output is correct |
13 |
Correct |
2794 ms |
10208 KB |
Output is correct |
14 |
Correct |
497 ms |
5876 KB |
Output is correct |
15 |
Correct |
2790 ms |
11328 KB |
Output is correct |
16 |
Correct |
870 ms |
12904 KB |
Output is correct |
17 |
Correct |
1502 ms |
10068 KB |
Output is correct |
18 |
Correct |
2558 ms |
14548 KB |
Output is correct |
19 |
Correct |
2147 ms |
14584 KB |
Output is correct |
20 |
Correct |
2182 ms |
13900 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
555 ms |
7612 KB |
Output is correct |
13 |
Correct |
298 ms |
11760 KB |
Output is correct |
14 |
Correct |
942 ms |
9344 KB |
Output is correct |
15 |
Correct |
1082 ms |
8744 KB |
Output is correct |
16 |
Correct |
728 ms |
7764 KB |
Output is correct |
17 |
Correct |
1036 ms |
9360 KB |
Output is correct |
18 |
Correct |
941 ms |
8796 KB |
Output is correct |
19 |
Correct |
1008 ms |
15416 KB |
Output is correct |
20 |
Correct |
2569 ms |
9876 KB |
Output is correct |
21 |
Correct |
475 ms |
5716 KB |
Output is correct |
22 |
Correct |
2743 ms |
10976 KB |
Output is correct |
23 |
Correct |
955 ms |
12852 KB |
Output is correct |
24 |
Correct |
1488 ms |
10020 KB |
Output is correct |
25 |
Correct |
2525 ms |
14404 KB |
Output is correct |
26 |
Correct |
2173 ms |
14672 KB |
Output is correct |
27 |
Correct |
2137 ms |
14040 KB |
Output is correct |
28 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 6 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
567 ms |
7464 KB |
Output is correct |
13 |
Correct |
293 ms |
11712 KB |
Output is correct |
14 |
Correct |
935 ms |
9120 KB |
Output is correct |
15 |
Correct |
1098 ms |
8744 KB |
Output is correct |
16 |
Correct |
738 ms |
7560 KB |
Output is correct |
17 |
Correct |
1046 ms |
8984 KB |
Output is correct |
18 |
Correct |
933 ms |
8612 KB |
Output is correct |
19 |
Correct |
1020 ms |
15484 KB |
Output is correct |
20 |
Correct |
2634 ms |
9984 KB |
Output is correct |
21 |
Correct |
483 ms |
5716 KB |
Output is correct |
22 |
Correct |
2760 ms |
11492 KB |
Output is correct |
23 |
Correct |
707 ms |
13148 KB |
Output is correct |
24 |
Correct |
1478 ms |
10072 KB |
Output is correct |
25 |
Correct |
2519 ms |
14856 KB |
Output is correct |
26 |
Correct |
2164 ms |
14932 KB |
Output is correct |
27 |
Correct |
2145 ms |
13928 KB |
Output is correct |
28 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 6 |
29 |
Halted |
0 ms |
0 KB |
- |