Submission #1248462

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

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;

/**
 * @struct SegTree2D
 * @brief A memory-efficient 2D dynamic segment tree template.
 *
 * This data structure is designed for 2D point updates and range queries on a sparse
 * grid. It is based on a segment tree of highly sparse segment trees, making it
 * extremely memory-efficient for problems with large coordinate spaces but
 * a relatively small number of points.
 *
 * @tparam T The data type of the values stored in the tree (e.g., long long, int).
 */
template<typename T>
struct SegTree2D {
private:
    // --- Data Members ---
    int R_min_dim, R_max_dim, C_min_dim, C_max_dim;
    T default_value;

    // --- Nested Node Structs ---

    // The inner tree for columns (y-axis). 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;
        T value;

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

    // The outer tree for rows (x-axis).
    struct Y_NODE {
        Y_NODE *left = nullptr, *right = nullptr;
        // Each row-node contains a root for a column-tree.
        X_NODE xtree;

        Y_NODE(int c_min, int c_max, T def_val) : xtree(c_min, c_max, def_val) {}
        ~Y_NODE() {
            delete left;
            delete right;
        }
    };

    Y_NODE* root = nullptr;


    int merge(int a, int b){
        return gcd(a, b);
    }
    // --- Private Helper Functions (Recursive Logic) ---

    // Update function for the inner/column tree (X_NODE)
    void update_y(X_NODE* node, int q, T 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) {
            *child_ptr = new X_NODE(q, q, default_value);
            (*child_ptr)->value = k;
        } else if ((*child_ptr)->s <= q && q <= (*child_ptr)->e) {
            update_y(*child_ptr, q, k);
        } else {
            int new_s = s, new_e = e, 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, default_value);
            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);
        }

        T left_val = node->left ? node->left->value : default_value;
        T right_val = node->right ? node->right->value : default_value;
        node->value = merge(left_val, right_val);
    }

    // Point query for the inner/column tree, needed for bottom-up updates.
    T query_y_point(X_NODE* node, int q) {
        if (node == nullptr || node->s > q || node->e < q) {
            return default_value;
        }
        if (node->s == node->e) {
            return node->value;
        }
        int m = node->s + (node->e - node->s) / 2;
        return (q <= m) ? query_y_point(node->left, q) : query_y_point(node->right, q);
    }

    // Range query for the inner/column tree.
    T query_y_range(X_NODE* node, int s, int e) {
        if (node == nullptr || node->s > e || node->e < s) {
            return default_value;
        }
        if (s <= node->s && node->e <= e) {
            return node->value;
        }
        return merge(query_y_range(node->left, s, e), query_y_range(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, T k) {
        if (s == e) {
            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(C_min_dim, C_max_dim, default_value);
            update_x(node->left, s, m, p, q, k);
        } else {
            if (node->right == nullptr) node->right = new Y_NODE(C_min_dim, C_max_dim, default_value);
            update_x(node->right, m + 1, e, p, q, k);
        }

        T left_val = node->left ? query_y_point(&node->left->xtree, q) : default_value;
        T right_val = node->right ? query_y_point(&node->right->xtree, q) : default_value;
        update_y(&node->xtree, q, merge(left_val, right_val));
    }

    // Query function for the outer/row tree (Y_NODE)
    T 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 default_value;
        }
        if (p <= s && e <= u) {
            return query_y_range(&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));
    }

public:
    /**
     * @brief Constructs the 2D Segment Tree.
     * @param r_min The minimum row coordinate.
     * @param r_max The maximum row coordinate.
     * @param c_min The minimum column coordinate.
     * @param c_max The maximum column coordinate.
     * @param def_val The default value for empty nodes (e.g., 0 for sum/gcd, infinity for min).
     */
    SegTree2D(int r_min, int r_max, int c_min, int c_max, T def_val = T{})
        : R_min_dim(r_min), R_max_dim(r_max), C_min_dim(c_min), C_max_dim(c_max), default_value(def_val) {
        root = new Y_NODE(C_min_dim, C_max_dim, default_value);
    }

    SegTree2D(){}


    /**
     * @brief Updates the value at a specific point in the grid.
     * @param P The row.
     * @param Q The column.
     * @param K The new value for the point.
     */
    void update(int P, int Q, T K) {
        update_x(root, R_min_dim, R_max_dim, P, Q, K);
    }

    /**
     * @brief Performs a range query on a rectangular area of the grid.
     * @param P The starting row of the rectangle.
     * @param Q The starting column of the rectangle.
     * @param U The ending row of the rectangle.
     * @param V The ending column of the rectangle.
     * @return The aggregated value in the specified rectangle.
     */
    T query(int P, int Q, int U, int V) {
        return query_x(root, R_min_dim, R_max_dim, P, Q, U, V);
    }
};

SegTree2D<int> st;

void init(int R, int C) {
    st = SegTree2D<int>(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, val;
//             cin >> p >> q >> val;
//             update(p, q, val);
//         }else{
//             int p, q, u, v;
//             cin >> p >> q >> u >> v;
//             cout << calculate(p, q, u, v) << "\n";
//         }
//     }
// }

// int main(){
//     ios_base::sync_with_stdio(0), cin.tie(0);
//     solve();
//     return 0;
// }

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