# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
954598 |
2024-03-28T08:02:18 Z |
islingr |
Game (IOI13_game) |
C++17 |
|
149 ms |
256000 KB |
#include "game.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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(root, 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) {
assert(n <= 100 and m <= 100);
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 |
344 KB |
Output is correct |
2 |
Runtime error |
149 ms |
256000 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Runtime error |
135 ms |
256000 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Runtime error |
143 ms |
256000 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Runtime error |
134 ms |
256000 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Runtime error |
133 ms |
256000 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |