Submission #1248481

#TimeUsernameProblemLanguageResultExecution timeMemory
1248481mazen_ghanayemGame (IOI13_game)C++20
100 / 100
2547 ms71640 KiB
#include "game.h" #include <bits/stdc++.h> #define ll long long // Use static global variables as in the accepted solution static int R_max_dim, C_max_dim, R_min_dim, C_min_dim; // Forward declarations struct X_NODE; struct Y_NODE; // Global root pointer static Y_NODE* root = nullptr; // Wrapper for GCD to handle the case where one value is 0 ll merge(ll x, ll y) { if (x == 0) return y; if (y == 0) return x; return std::gcd(x, y); } // The inner tree for columns. This is a highly sparse, custom segment tree. struct X_NODE { int s, e; // The range this node is responsible for [s, e] X_NODE *left = nullptr, *right = nullptr; ll value = 0LL; X_NODE(int s, int e) : s(s), e(e) {} ~X_NODE() { delete left; delete right; } }; // The outer tree for rows. This is a more standard dynamic segment tree. struct Y_NODE { Y_NODE *left = nullptr, *right = nullptr; // Each row-node contains a root for a column-tree. // It's initialized with the full column range. X_NODE xtree; Y_NODE() : xtree(1, C_max_dim) {} ~Y_NODE() { delete left; delete right; } }; // --- Core Functions Matching the Accepted Solution --- // Update function for the inner/column tree (X_NODE) void update_y(X_NODE* node, int q, ll k) { int s = node->s, e = node->e; if (s == e) { node->value = k; return; } int m = s + (e - s) / 2; X_NODE** child_ptr = (q <= m) ? &(node->left) : &(node->right); if (*child_ptr == nullptr) { // Optimization: If no child exists, create a single leaf node directly. // This avoids creating the full path and is the key memory saver. *child_ptr = new X_NODE(q, q); (*child_ptr)->value = k; } else if ((*child_ptr)->s <= q && q <= (*child_ptr)->e) { // Child exists and its range covers the target point, so recurse. update_y(*child_ptr, q, k); } else { // Tricky case: Child exists but doesn't cover the point. // We need to create a new parent to hold both the old child and the new point. int new_s = s, new_e = e; int new_m = m; do { if (q <= new_m) new_e = new_m; else new_s = new_m + 1; new_m = new_s + (new_e - new_s) / 2; } while ((q <= new_m) == ((*child_ptr)->e <= new_m)); X_NODE* new_node = new X_NODE(new_s, new_e); if ((*child_ptr)->e <= new_m) { new_node->left = *child_ptr; } else { new_node->right = *child_ptr; } *child_ptr = new_node; update_y(*child_ptr, q, k); } // After recursion, update this node's value ll left_val = node->left ? node->left->value : 0; ll right_val = node->right ? node->right->value : 0; node->value = merge(left_val, right_val); } // Query function for the inner/column tree (X_NODE) ll query_y(X_NODE* node, int s, int e) { if (node == nullptr || node->s > e || node->e < s) { return 0; } if (s <= node->s && node->e <= e) { return node->value; } return merge(query_y(node->left, s, e), query_y(node->right, s, e)); } // Update function for the outer/row tree (Y_NODE) void update_x(Y_NODE* node, int s, int e, int p, int q, ll k) { if (s == e) { // Reached the leaf row, update its column tree update_y(&node->xtree, q, k); return; } int m = s + (e - s) / 2; if (p <= m) { if (node->left == nullptr) node->left = new Y_NODE(); update_x(node->left, s, m, p, q, k); } else { if (node->right == nullptr) node->right = new Y_NODE(); update_x(node->right, m + 1, e, p, q, k); } // Bottom-up update: query children to update this node's column tree ll left_val = node->left ? query_y(&node->left->xtree, q, q) : 0; ll right_val = node->right ? query_y(&node->right->xtree, q, q) : 0; update_y(&node->xtree, q, merge(left_val, right_val)); } // Query function for the outer/row tree (Y_NODE) ll query_x(Y_NODE* node, int s, int e, int p, int q, int u, int v) { if (node == nullptr || s > u || e < p) { return 0; } if (p <= s && e <= u) { // This row range is fully contained, query its column tree return query_y(&node->xtree, q, v); } int m = s + (e - s) / 2; return merge(query_x(node->left, s, m, p, q, u, v), query_x(node->right, m + 1, e, p, q, u, v)); } void updateval(int x, int y, long long val){ update_x(root, R_min_dim, R_max_dim, x, y, val); } ll query(int x1, int y1, int x2, int y2){ return query_x(root, R_min_dim, R_max_dim, x1, y1, x2, y2); } // --- Interface Functions --- void init(int R, int C) { R_min_dim = 1; C_min_dim = 1; R_max_dim = R; C_max_dim = C; delete root; // Delete old tree if it exists from a previous test case root = new Y_NODE(); } void update(int P, int Q, long long K) { updateval(P + 1, Q + 1, K); } long long calculate(int P, int Q, int U, int V) { return query(P + 1, Q + 1, U + 1, V + 1); }
#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...