Submission #1248426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248426		mazen_ghanayem	Game (IOI13_game)	C++20	0 / 100	0 ms	328 KiB

game

#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 st;

void init(int R, int C) {
    st = DynamicSegTree2D(0, R - 1, 0, C - 1);
}

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);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20