#include "game.h" // MEMORY CALCULATION: // NodeY: 16 bytes * 13,000,000 ~= 208 MB // NodeX: 12 bytes * 700,000 ~= 8.4 MB // Total Static: ~216.4 MB (Leaves ~33 MB for stack/overhead within 250 MB) const int NODE_Y_MAX = 13000000; const int NODE_X_MAX = 700000; const int NMAX = 1e9; #define ll long long long long gcd2(long long X, long long Y) { long long tmp; while (Y != 0) { tmp = X; X = Y; Y = tmp % Y; } return X; } int n, m, root_x; int nodes_y = 0; int nodes_x = 0; struct NodeY { ll gcd; int left, right; } aint_y[NODE_Y_MAX + 2]; // +2 for safety 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; // Safety check return ++nodes_x; } int create_node_y() { if (nodes_y >= NODE_Y_MAX) return 0; // Safety check return ++nodes_y; } void updateY(int& node, int left, int right, int pos, ll value) { if(!node) { node = create_node_y(); if (!node) return; // Out of memory } if(left == right) { aint_y[node].gcd = value; return; } int mid = (left + right) >> 1; // Bitwise shift is slightly faster if(pos <= mid) { updateY(aint_y[node].left, left, mid, pos, value); } else { updateY(aint_y[node].right, mid + 1, right, pos, value); } // Recalculate current node's GCD from children 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 = gcd2(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 gcd2(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) { // Leaf in X-tree: Just update the Y-tree 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); } // --- CRITICAL MEMORY OPTIMIZATION --- // 1. Calculate what the new GCD for this (pos_y) SHOULD be based on children 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 = gcd2(val_left, val_right); // 2. Check what is CURRENTLY stored at this (pos_y) in this node's Y-tree ll current_stored_gcd = queryY(aint_x[node].root_y, 1, m, pos_y, pos_y); // 3. Only update if the value actually changes. // This prevents creating a path of ~30 nodes in the Y-tree for every X-update // when the GCD remains stable (common in sparse grids). if (new_gcd != current_stored_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 gcd2(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; // Clear roots if necessary for multiple test cases, // but IOI tasks usually run once per execution. 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); }