Submission #545973

#TimeUsernameProblemLanguageResultExecution timeMemory
545973sliviuGame (IOI13_game)C++17
100 / 100
2904 ms82160 KiB
#include "game.h" #include <stdlib.h> typedef long long ll; static int R, C; struct X_NODE { X_NODE(int s, int e) : s(s), e(e), left(NULL), right(NULL), value(0LL) {} int s, e; X_NODE* left, * right; ll value; }; struct Y_NODE { Y_NODE() : left(NULL), right(NULL), xtree(1, C) {} Y_NODE* left, * right; X_NODE xtree; } *root; ll gcd2(ll x, ll y) { if (y == 0) return x; return gcd2(y, x % y); } void init(int r, int c) { R = r, C = c; root = new Y_NODE(); } void update2(X_NODE* node, int q, ll k) { int s = node->s, e = node->e, m = (s + e) >> 1; if (s == e) { node->value = k; return; } X_NODE*& child = (q <= m ? node->left : node->right); if (child == NULL) { child = new X_NODE(q, q); (child)->value = k; } else if ((child)->s <= q && q <= (child)->e) { update2(child, q, k); } else { do { if (q <= m) e = m; else s = m + 1; m = (s + e) >> 1; } while ((q <= m) == ((child)->e <= m)); X_NODE* nnode = new X_NODE(s, e); if ((child)->e <= m) nnode->left = child; else nnode->right = child; child = nnode; update2(child, q, k); } node->value = gcd2( node->left ? node->left->value : 0, node->right ? node->right->value : 0 ); } ll query2(X_NODE* node, int s, int e) { if (node == NULL || node->s > e || node->e < s) return 0; if (s <= node->s && node->e <= e) { return node->value; } return gcd2(query2(node->left, s, e), query2(node->right, s, e)); } void update1(Y_NODE* node, int s, int e, int p, int q, ll k) { int m = (s + e) >> 1; if (s == e) { update2(&node->xtree, q, k); return; } if (p <= m) { if (node->left == NULL) node->left = new Y_NODE(); update1(node->left, s, m, p, q, k); } else { if (node->right == NULL) node->right = new Y_NODE(); update1(node->right, m + 1, e, p, q, k); } ll v = gcd2( node->left ? query2(&node->left->xtree, q, q) : 0, node->right ? query2(&node->right->xtree, q, q) : 0 ); update2(&node->xtree, q, v); } void update(int p, int q, ll k) { ++p, ++q; update1(root, 1, R, p, q, k); } ll query1(Y_NODE* node, int s, int e, int p, int q, int u, int v) { if (node == NULL || s > u || e < p) return 0; if (p <= s && e <= u) return query2(&node->xtree, q, v); int m = (s + e) >> 1; return gcd2( query1(node->left, s, m, p, q, u, v), query1(node->right, m + 1, e, p, q, u, v) ); } ll calculate(int p, int q, int u, int v) { ++p, ++q, ++u, ++v; return query1(root, 1, R, p, q, u, v); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...