#include "game.h" #include <algorithm> // For std::swap and __gcd #define ll long long // MAXIMIZED MEMORY LIMITS (Targeting ~248MiB total) const int NODE_Y_MAX = 14800000; // ~236.8 MB const int NODE_X_MAX = 1000000; // ~11.4 MB const int NMAX = 1e9; // Use built-in GCD for speed (GCC builtin), or fallback to manual if needed. // __gcd is available in <algorithm> in most competitive programming environments. long long gcd_algo(long long a, long long b) { return std::__gcd(a, b); } int n, m, root_x; int nodes_y = 0; int nodes_x = 0; // Packed structures to ensure no padding bytes are wasted struct NodeY { ll gcd; int left, right; } aint_y[NODE_Y_MAX + 2]; struct NodeX { int root_y; int left, right; } aint_x[NODE_X_MAX + 2]; int create_node_x() { if (nodes_x >= NODE_X_MAX) return 0; // Prevent SEGFAULT if limit reached return ++nodes_x; } int create_node_y() { if (nodes_y >= NODE_Y_MAX) return 0; // Prevent SEGFAULT if limit reached return ++nodes_y; } void updateY(int& node, int left, int right, int pos, ll value) { if(!node) { node = create_node_y(); if(!node) return; // Safety exit if OOM } if(left == right) { aint_y[node].gcd = value; return; } int mid = (left + right) >> 1; if(pos <= mid) { updateY(aint_y[node].left, left, mid, pos, value); } else { updateY(aint_y[node].right, mid + 1, right, pos, value); } ll left_gcd = aint_y[node].left ? aint_y[aint_y[node].left].gcd : 0; ll right_gcd = aint_y[node].right ? aint_y[aint_y[node].right].gcd : 0; aint_y[node].gcd = gcd_algo(left_gcd, right_gcd); } ll queryY(int node, int left, int right, int qleft, int qright) { if(!node || left > qright || right < qleft) { return 0; } if(left >= qleft && right <= qright) { return aint_y[node].gcd; } int mid = (left + right) >> 1; return gcd_algo(queryY(aint_y[node].left, left, mid, qleft, qright), queryY(aint_y[node].right, mid + 1, right, qleft, qright)); } void updateX(int& node, int left_x, int right_x, int pos_x, int pos_y, ll value) { if(!node) { node = create_node_x(); if(!node) return; } if(left_x == right_x) { updateY(aint_x[node].root_y, 1, m, pos_y, value); return; } int mid_x = (left_x + right_x) >> 1; if(pos_x <= mid_x) { updateX(aint_x[node].left, left_x, mid_x, pos_x, pos_y, value); } else { updateX(aint_x[node].right, mid_x + 1, right_x, pos_x, pos_y, value); } // --- OPTIMIZATION: Check before update --- // Calculate what the new GCD *would* be for this column ll val_left = 0, val_right = 0; if (aint_x[node].left) val_left = queryY(aint_x[aint_x[node].left].root_y, 1, m, pos_y, pos_y); if (aint_x[node].right) val_right = queryY(aint_x[aint_x[node].right].root_y, 1, m, pos_y, pos_y); ll new_gcd = gcd_algo(val_left, val_right); // Get the current existing GCD in the tree ll current_gcd = queryY(aint_x[node].root_y, 1, m, pos_y, pos_y); // Only commit the update to the Y-tree if the value effectively changes. // This saves massive amounts of memory on the path up the X-tree. if (new_gcd != current_gcd) { updateY(aint_x[node].root_y, 1, m, pos_y, new_gcd); } } ll queryX(int node, int left_x, int right_x, int qleft_x, int qleft_y, int qright_x, int qright_y) { if(!node || left_x > qright_x || right_x < qleft_x) { return 0; } if(left_x >= qleft_x && right_x <= qright_x) { return queryY(aint_x[node].root_y, 1, m, qleft_y, qright_y); } int mid_x = (left_x + right_x) >> 1; return gcd_algo(queryX(aint_x[node].left, left_x, mid_x, qleft_x, qleft_y, qright_x, qright_y), queryX(aint_x[node].right, mid_x + 1, right_x, qleft_x, qleft_y, qright_x, qright_y)); } void init(int R, int C) { n = R; m = C; nodes_x = 0; nodes_y = 0; root_x = create_node_x(); } void update(int P, int Q, long long K) { updateX(root_x, 1, n, P + 1, Q + 1, K); } long long calculate(int P, int Q, int U, int V) { return queryX(root_x, 1, n, P + 1, Q + 1, U + 1, V + 1); }