Submission #1248432

#TimeUsernameProblemLanguageResultExecution timeMemory
1248432mazen_ghanayemGame (IOI13_game)C++20
0 / 100
1 ms320 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; // Define long long for convenience //#define int long long #define ll long long /** * @struct DynamicSegTree2D * @brief Implements a 2D Dynamic Segment Tree. * * This data structure is useful for performing 2D range queries (e.g., sum, min, max) * and point updates on a very large or sparse 2D grid. It avoids allocating * memory for the entire grid by creating nodes only when they are needed. * * The structure is essentially a dynamic segment tree of dynamic segment trees. * The "outer" or "x-tree" segments the rows (first dimension), and each of its nodes * contains a pointer to another "inner" or "y-tree" that segments the columns * (second dimension) for that row range. * * @tparam T The data type of the values stored in the tree. * @tparam M The merge operation function (e.g., plus, minimum, maximum). */ struct DynamicSegTree2D { // The default value for nodes that don't exist and for query results on empty ranges. ll DEFAULT_VALUE; /** * @brief Merges two values. This is the core operation of the segment tree. * @param a The first value. * @param b The second value. * @return The result of merging a and b. */ ll merge(ll a, ll b) { return gcd(a, b); } // --- Inner Segment Tree (for columns/y-axis) --- struct NodeY { ll val; NodeY *left = nullptr, *right = nullptr; NodeY(ll v = 0) : val(v) {} // Safely get value from a node, returning default if null ll left_val() { return left ? left->val : 0; } ll right_val() { return right ? right->val : 0; } }; // --- Outer Segment Tree (for rows/x-axis) --- struct NodeX { NodeY* y_tree = nullptr; // Pointer to the root of the column segment tree NodeX *left = nullptr, *right = nullptr; }; NodeX* root; ll min_x, max_x, min_y, max_y; /** * @brief Constructor for the 2D Dynamic Segment Tree. * @param min_coord_x The minimum possible x-coordinate. * @param max_coord_x The maximum possible x-coordinate. * @param min_coord_y The minimum possible y-coordinate. * @param max_coord_y The maximum possible y-coordinate. */ DynamicSegTree2D(ll min_coord_x, ll max_coord_x, ll min_coord_y, ll max_coord_y) : min_x(min_coord_x), max_x(max_coord_x), min_y(min_coord_y), max_y(max_coord_y) { root = new NodeX(); DEFAULT_VALUE = 0; } DynamicSegTree2D(){} // --- Update Functions --- /** * @brief Updates the value in the inner y-tree (columns). */ void update_y(NodeY*& node, ll y, ll val, ll cur_min_y, ll cur_max_y) { if (!node) { node = new NodeY(); } if (cur_min_y == cur_max_y) { node->val = val; // Update the value at the target y-coordinate return; } ll mid_y = cur_min_y + (cur_max_y - cur_min_y) / 2; if (y <= mid_y) { update_y(node->left, y, val, cur_min_y, mid_y); } else { update_y(node->right, y, val, mid_y + 1, cur_max_y); } node->val = merge(node->left_val(), node->right_val()); } /** * @brief Updates the value in the outer x-tree (rows), propagating to the y-trees. */ void update_x(NodeX*& node, ll x, ll y, ll val, ll cur_min_x, ll cur_max_x) { if (!node) { node = new NodeX(); } // Update the corresponding y-tree at this x-node update_y(node->y_tree, y, val, min_y, max_y); if (cur_min_x == cur_max_x) { return; } ll mid_x = cur_min_x + (cur_max_x - cur_min_x) / 2; if (x <= mid_x) { update_x(node->left, x, y, val, cur_min_x, mid_x); } else { update_x(node->right, x, y, val, mid_x + 1, cur_max_x); } } /** * @brief Public interface for updating a value at a specific (x, y) coordinate. * @param x The x-coordinate. * @param y The y-coordinate. * @param val The value to add. */ void update(ll x, ll y, ll val) { update_x(root, x, y, val, min_x, max_x); } // --- Query Functions --- /** * @brief Performs a range query on the inner y-tree (columns). */ ll query_y(NodeY* node, ll y1, ll y2, ll cur_min_y, ll cur_max_y) { if (!node || y1 > cur_max_y || y2 < cur_min_y) { return DEFAULT_VALUE; } if (y1 <= cur_min_y && y2 >= cur_max_y) { return node->val; } ll mid_y = cur_min_y + (cur_max_y - cur_min_y) / 2; ll left_res = query_y(node->left, y1, y2, cur_min_y, mid_y); ll right_res = query_y(node->right, y1, y2, mid_y + 1, cur_max_y); return merge(left_res, right_res); } /** * @brief Performs a range query on the outer x-tree (rows). */ ll query_x(NodeX* node, ll x1, ll x2, ll y1, ll y2, ll cur_min_x, ll cur_max_x) { if (!node || x1 > cur_max_x || x2 < cur_min_x) { return DEFAULT_VALUE; } if (x1 <= cur_min_x && x2 >= cur_max_x) { // This node's x-range is fully contained, so query its y-tree return query_y(node->y_tree, y1, y2, min_y, max_y); } ll mid_x = cur_min_x + (cur_max_x - cur_min_x) / 2; ll left_res = query_x(node->left, x1, x2, y1, y2, cur_min_x, mid_x); ll right_res = query_x(node->right, x1, x2, y1, y2, mid_x + 1, cur_max_x); return merge(left_res, right_res); } /** * @brief Public interface for a 2D range query. * @param x1 The starting x-coordinate of the query rectangle. * @param y1 The starting y-coordinate of the query rectangle. * @param x2 The ending x-coordinate of the query rectangle. * @param y2 The ending y-coordinate of the query rectangle. * @return The aggregated value in the specified rectangle. */ ll query(ll x1, ll y1, ll x2, ll y2) { return query_x(root, x1, x2, y1, y2, min_x, max_x); } ~DynamicSegTree2D() { // Destructor to clean up memory delete_tree(root); } void delete_tree(NodeX* node) { if (!node) return; delete_tree(node->left); delete_tree(node->right); delete node->y_tree; // Clean up the y-tree delete node; } }; DynamicSegTree2D st; void init(int R, int C) { st = DynamicSegTree2D(0, R, 0, C); } void update(int P, int Q, long long K) { st.update(P, Q, K); } long long calculate(int P, int Q, int U, int V) { return st.query(P, Q, U, V); } // void solve() { // int R, C, Q; // cin >> R >> C >> Q; // init(R, C); // while (Q--) { // int type; // cin >> type; // if (type == 1) { // int P, Q, K; // cin >> P >> Q >> K; // update(P, Q, K); // } else if (type == 2) { // int P, Q, U, V; // cin >> P >> Q >> U >> V; // cout << calculate(P, Q, U, V) << '\n'; // } // } // } // int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // solve(); // return 0; // }
#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...