# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
954611 |
2024-03-28T08:21:01 Z |
islingr |
Game (IOI13_game) |
C++17 |
|
2841 ms |
11472 KB |
#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];
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);
}
# |
Verdict |
Execution time |
Memory |
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 |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
589 ms |
7560 KB |
Output is correct |
5 |
Correct |
262 ms |
7760 KB |
Output is correct |
6 |
Correct |
959 ms |
4628 KB |
Output is correct |
7 |
Correct |
1087 ms |
4644 KB |
Output is correct |
8 |
Correct |
725 ms |
3488 KB |
Output is correct |
9 |
Correct |
1067 ms |
4776 KB |
Output is correct |
10 |
Correct |
966 ms |
4376 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
0 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1101 ms |
11472 KB |
Output is correct |
13 |
Correct |
2666 ms |
8140 KB |
Output is correct |
14 |
Correct |
506 ms |
8428 KB |
Output is correct |
15 |
Correct |
2777 ms |
8684 KB |
Output is correct |
16 |
Correct |
811 ms |
8528 KB |
Output is correct |
17 |
Correct |
1509 ms |
5132 KB |
Output is correct |
18 |
Correct |
2544 ms |
9288 KB |
Output is correct |
19 |
Correct |
2189 ms |
9156 KB |
Output is correct |
20 |
Correct |
2161 ms |
8568 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 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 |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
592 ms |
7480 KB |
Output is correct |
13 |
Correct |
260 ms |
7728 KB |
Output is correct |
14 |
Correct |
954 ms |
4776 KB |
Output is correct |
15 |
Correct |
1075 ms |
4404 KB |
Output is correct |
16 |
Correct |
748 ms |
3408 KB |
Output is correct |
17 |
Correct |
1064 ms |
4292 KB |
Output is correct |
18 |
Correct |
934 ms |
3860 KB |
Output is correct |
19 |
Correct |
1085 ms |
11240 KB |
Output is correct |
20 |
Correct |
2730 ms |
8016 KB |
Output is correct |
21 |
Correct |
479 ms |
8296 KB |
Output is correct |
22 |
Correct |
2841 ms |
8780 KB |
Output is correct |
23 |
Correct |
896 ms |
8564 KB |
Output is correct |
24 |
Correct |
1488 ms |
5328 KB |
Output is correct |
25 |
Correct |
2529 ms |
9040 KB |
Output is correct |
26 |
Correct |
2204 ms |
9016 KB |
Output is correct |
27 |
Correct |
2192 ms |
8776 KB |
Output is correct |
28 |
Runtime error |
3 ms |
600 KB |
Execution killed with signal 6 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
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 |
344 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 |
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 |
592 ms |
7356 KB |
Output is correct |
13 |
Correct |
274 ms |
8276 KB |
Output is correct |
14 |
Correct |
940 ms |
4688 KB |
Output is correct |
15 |
Correct |
1109 ms |
4132 KB |
Output is correct |
16 |
Correct |
728 ms |
3588 KB |
Output is correct |
17 |
Correct |
1057 ms |
4452 KB |
Output is correct |
18 |
Correct |
953 ms |
4232 KB |
Output is correct |
19 |
Correct |
972 ms |
11308 KB |
Output is correct |
20 |
Correct |
2672 ms |
8044 KB |
Output is correct |
21 |
Correct |
497 ms |
8440 KB |
Output is correct |
22 |
Correct |
2776 ms |
8636 KB |
Output is correct |
23 |
Correct |
811 ms |
8592 KB |
Output is correct |
24 |
Correct |
1528 ms |
5480 KB |
Output is correct |
25 |
Correct |
2577 ms |
9012 KB |
Output is correct |
26 |
Correct |
2160 ms |
9048 KB |
Output is correct |
27 |
Correct |
2137 ms |
8592 KB |
Output is correct |
28 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 6 |
29 |
Halted |
0 ms |
0 KB |
- |