Submission #1248484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248484		mazen_ghanayem	Game (IOI13_game)	C++20	100 / 100	2625 ms	71580 KiB

game

#include "game.h"
#include <bits/stdc++.h>

#define ll long long

// Use static global variables as in the accepted solution
static int R_max_dim, C_max_dim, R_min_dim, C_min_dim;

// Forward declarations
struct X_NODE;
struct Y_NODE;

// Global root pointer
static Y_NODE* root = nullptr;

// Wrapper for GCD to handle the case where one value is 0
ll merge(ll x, ll y) {
    if (x == 0) return y;
    if (y == 0) return x;
    return std::gcd(x, y);
}

// The inner tree for columns. This is a highly sparse, custom segment tree.
struct X_NODE {
    int s, e; // The range this node is responsible for [s, e]
    X_NODE *left = nullptr, *right = nullptr;
    ll value = 0LL;

    X_NODE(int s, int e) : s(s), e(e) {}
    ~X_NODE() {
        delete left;
        delete right;
    }
};

// The outer tree for rows. This is a more standard dynamic segment tree.
struct Y_NODE {
    Y_NODE *left = nullptr, *right = nullptr;
    // Each row-node contains a root for a column-tree.
    // It's initialized with the full column range.
    X_NODE xtree;

    Y_NODE() : xtree(C_min_dim, C_max_dim) {}
     ~Y_NODE() {
        delete left;
        delete right;
    }
};


// --- Core Functions Matching the Accepted Solution ---

// Update function for the inner/column tree (X_NODE)
void update_y(X_NODE* node, int q, ll k) {
    int s = node->s, e = node->e;
    if (s == e) {
        node->value = k;
        return;
    }
    
    int m = s + (e - s) / 2;
    X_NODE** child_ptr = (q <= m) ? &(node->left) : &(node->right);

    if (*child_ptr == nullptr) {
        // Optimization: If no child exists, create a single leaf node directly.
        // This avoids creating the full path and is the key memory saver.
        *child_ptr = new X_NODE(q, q);
        (*child_ptr)->value = k;
    } else if ((*child_ptr)->s <= q && q <= (*child_ptr)->e) {
        // Child exists and its range covers the target point, so recurse.
        update_y(*child_ptr, q, k);
    } else {
        // Tricky case: Child exists but doesn't cover the point.
        // We need to create a new parent to hold both the old child and the new point.
        int new_s = s, new_e = e;
        int new_m = m;
        do {
            if (q <= new_m) new_e = new_m;
            else new_s = new_m + 1;
            new_m = new_s + (new_e - new_s) / 2;
        } while ((q <= new_m) == ((*child_ptr)->e <= new_m));

        X_NODE* new_node = new X_NODE(new_s, new_e);
        if ((*child_ptr)->e <= new_m) {
            new_node->left = *child_ptr;
        } else {
            new_node->right = *child_ptr;
        }
        *child_ptr = new_node;
        update_y(*child_ptr, q, k);
    }

    // After recursion, update this node's value
    ll left_val = node->left ? node->left->value : 0;
    ll right_val = node->right ? node->right->value : 0;
    node->value = merge(left_val, right_val);
}

// Query function for the inner/column tree (X_NODE)
ll query_y(X_NODE* node, int s, int e) {
    if (node == nullptr || node->s > e || node->e < s) {
        return 0;
    }
    if (s <= node->s && node->e <= e) {
        return node->value;
    }
    return merge(query_y(node->left, s, e), query_y(node->right, s, e));
}

// Update function for the outer/row tree (Y_NODE)
void update_x(Y_NODE* node, int s, int e, int p, int q, ll k) {
    if (s == e) {
        // Reached the leaf row, update its column tree
        update_y(&node->xtree, q, k);
        return;
    }

    int m = s + (e - s) / 2;
    if (p <= m) {
        if (node->left == nullptr) node->left = new Y_NODE();
        update_x(node->left, s, m, p, q, k);
    } else {
        if (node->right == nullptr) node->right = new Y_NODE();
        update_x(node->right, m + 1, e, p, q, k);
    }

    // Bottom-up update: query children to update this node's column tree
    ll left_val = node->left ? query_y(&node->left->xtree, q, q) : 0;
    ll right_val = node->right ? query_y(&node->right->xtree, q, q) : 0;
    update_y(&node->xtree, q, merge(left_val, right_val));
}

// Query function for the outer/row tree (Y_NODE)
ll query_x(Y_NODE* node, int s, int e, int p, int q, int u, int v) {
    if (node == nullptr || s > u || e < p) {
        return 0;
    }
    if (p <= s && e <= u) {
        // This row range is fully contained, query its column tree
        return query_y(&node->xtree, q, v);
    }
    int m = s + (e - s) / 2;
    return merge(query_x(node->left, s, m, p, q, u, v),
                       query_x(node->right, m + 1, e, p, q, u, v));
}

void updateval(int x, int y, long long val){
    update_x(root, R_min_dim, R_max_dim, x, y, val);
}

ll query(int x1, int y1, int x2, int y2){
    return query_x(root, R_min_dim, R_max_dim, x1, y1, x2, y2);
}
// --- Interface Functions ---

void init(int R, int C) {
    R_min_dim = 0;
    C_min_dim = 0;
    R_max_dim = R;
    C_max_dim = C;
    delete root; // Delete old tree if it exists from a previous test case
    root = new Y_NODE();
}

void update(int P, int Q, long long K) {
    updateval(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query(P, Q, U, V);
}

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