Submission #1248452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248452		mazen_ghanayem	Game (IOI13_game)	C++20	63 / 100	1255 ms	278792 KiB

game

#include "game.h"
#include <numeric> // For std::gcd
#include <algorithm> // For std::min/max

using namespace std;
#define ll long long

// Forward declaration
struct DynamicSegTree2D;

// Global pointer to our tree instance
static DynamicSegTree2D* st = nullptr;
static int R_dim, C_dim;


ll gcd_wrapper(ll a, ll b) {
    if (a == 0) return b;
    if (b == 0) return a;
    return std::gcd(a, b);
}

/**
 * @struct DynamicSegTree2D
 * @brief Correctly implements a 2D Dynamic Segment Tree using bottom-up updates.
 *
 * This structure is a segment tree over rows (NodeX), where each node
 * contains a pointer to a segment tree over columns (NodeY).
 */
struct DynamicSegTree2D {
    static constexpr ll DEFAULT_VALUE = 0;

    ll merge(ll a, ll b) {
        return gcd_wrapper(a, b);
    }

    // --- Inner Segment Tree (for columns) ---
    struct NodeY {
        ll val = DEFAULT_VALUE;
        NodeY *left = nullptr, *right = nullptr;
        
        ~NodeY() { // Destructor to prevent memory leaks
            delete left;
            delete right;
        }
    };

    // --- Outer Segment Tree (for rows) ---
    struct NodeX {
        NodeY* y_tree = nullptr; // Pointer to the root of the column segment tree
        NodeX *left = nullptr, *right = nullptr;
        ~NodeX() { // Destructor
            delete y_tree;
            delete left;
            delete right;
        }
    };

    NodeX* root = nullptr;

    DynamicSegTree2D() {
        root = new NodeX();
    }
    ~DynamicSegTree2D() {
        delete root;
    }

    // --- Update Functions ---

    // Point update on a 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;
            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);
        }
        ll left_val = node->left ? node->left->val : DEFAULT_VALUE;
        ll right_val = node->right ? node->right->val : DEFAULT_VALUE;
        node->val = merge(left_val, right_val);
    }

    // Point query on a Y-tree (columns)
    ll query_y_point(NodeY* node, ll y, ll cur_min_y, ll cur_max_y) {
        if (!node || cur_min_y > y || cur_max_y < y) {
            return DEFAULT_VALUE;
        }
        if (cur_min_y == cur_max_y) {
            return node->val;
        }
        ll mid_y = cur_min_y + (cur_max_y - cur_min_y) / 2;
        if (y <= mid_y) {
            return query_y_point(node->left, y, cur_min_y, mid_y);
        } else {
            return query_y_point(node->right, y, mid_y + 1, cur_max_y);
        }
    }

    // Main update function for the X-tree (rows)
    void update_x(NodeX*& node, ll x, ll y, ll val, ll cur_min_x, ll cur_max_x) {
        if (!node) {
            node = new NodeX();
        }
        if (cur_min_x == cur_max_x) {
            // We are at a leaf in the row tree, update its column tree
            update_y(node->y_tree, y, val, 1, C_dim);
            return;
        }

        // Recurse down to find the correct row leaf
        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);
        }

        // *** THE CRITICAL STEP (BOTTOM-UP PROPAGATION) ***
        // After child is updated, query children to update this node's column tree
        ll left_y_val = node->left ? query_y_point(node->left->y_tree, y, 1, C_dim) : DEFAULT_VALUE;
        ll right_y_val = node->right ? query_y_point(node->right->y_tree, y, 1, C_dim) : DEFAULT_VALUE;
        
        update_y(node->y_tree, y, merge(left_y_val, right_y_val), 1, C_dim);
    }

    // --- Query Functions ---

    // Range query on a Y-tree (columns)
    ll query_y_range(NodeY* node, ll y1, ll y2, ll cur_min_y, ll cur_max_y) {
        if (!node || y1 > y2 || 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_range(node->left, y1, min(y2, mid_y), cur_min_y, mid_y);
        ll right_res = query_y_range(node->right, max(y1, mid_y + 1), y2, mid_y + 1, cur_max_y);
        return merge(left_res, right_res);
    }

    // Main query function for the 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 > x2 || x1 > cur_max_x || x2 < cur_min_x) {
            return DEFAULT_VALUE;
        }
        if (x1 <= cur_min_x && x2 >= cur_max_x) {
            // This node's row-range is fully contained, query its column-tree
            return query_y_range(node->y_tree, y1, y2, 1, C_dim);
        }

        ll mid_x = cur_min_x + (cur_max_x - cur_min_x) / 2;
        ll left_res = query_x(node->left, x1, min(x2, mid_x), y1, y2, cur_min_x, mid_x);
        ll right_res = query_x(node->right, max(x1, mid_x + 1), x2, y1, y2, mid_x + 1, cur_max_x);
        return merge(left_res, right_res);
    }
};

// --- Interface Functions ---

void init(int R, int C) {
    R_dim = R;
    C_dim = C;
    delete st; // Delete old tree if it exists
    st = new DynamicSegTree2D();
}

void update(int P, int Q, long long K) {
    if (st) {
        st->update_x(st->root, P + 1, Q + 1, K, 1, R_dim);
    }
}

long long calculate(int P, int Q, int U, int V) {
    if (st) {
        return st->query_x(st->root, P + 1, U + 1, Q + 1, V + 1, 1, R_dim);
    }
    return 0;
}

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