Submission #1306828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306828		orzorzorz	Game (IOI13_game)	C++20	100 / 100	4740 ms	28584 KiB

game

#include "game.h"
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef long long ll;

// Helper: GCD of two numbers (provided by problem statement)
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

// ---------------------------------------------------------
// INNER DATA STRUCTURE: TREAP (Handles Columns)
// ---------------------------------------------------------
struct TreapNode {
    int left_idx;   // Index in pool
    int right_idx;  // Index in pool
    int key;        // Column index
    int prio;       // Random priority
    ll val;         // Value at this specific column
    ll gcd_val;     // GCD of the whole subtree
};

// Memory Pool for Treap
const int MAX_TREAP_NODES = 6000000; // Sufficient for Nu * log(R) * const
TreapNode treap_pool[MAX_TREAP_NODES];
int treap_ptr = 1; // 0 is reserved for NULL

// Helper to get GCD of a node (handles 0/NULL index gracefully)
ll get_treap_gcd(int t_idx) {
    return (t_idx == 0) ? 0 : treap_pool[t_idx].gcd_val;
}

// Update the gcd_val of a node based on children
void pull_treap(int t_idx) {
    if (t_idx == 0) return;
    ll l_gcd = get_treap_gcd(treap_pool[t_idx].left_idx);
    ll r_gcd = get_treap_gcd(treap_pool[t_idx].right_idx);
    treap_pool[t_idx].gcd_val = gcd2(treap_pool[t_idx].val, gcd2(l_gcd, r_gcd));
}

// Create new node
int new_treap_node(int key, ll val) {
    int idx = treap_ptr++;
    treap_pool[idx].left_idx = 0;
    treap_pool[idx].right_idx = 0;
    treap_pool[idx].key = key;
    treap_pool[idx].prio = rand();
    treap_pool[idx].val = val;
    treap_pool[idx].gcd_val = val;
    return idx;
}

// Split Treap by key
void split(int t, int key, int &l, int &r) {
    if (t == 0) {
        l = r = 0;
    } else if (treap_pool[t].key <= key) {
        split(treap_pool[t].right_idx, key, treap_pool[t].right_idx, r);
        l = t;
    } else {
        split(treap_pool[t].left_idx, key, l, treap_pool[t].left_idx);
        r = t;
    }
    pull_treap(t);
}

// Merge two Treaps
void merge(int &t, int l, int r) {
    if (l == 0 || r == 0) {
        t = (l != 0) ? l : r;
    } else if (treap_pool[l].prio > treap_pool[r].prio) {
        merge(treap_pool[l].right_idx, treap_pool[l].right_idx, r);
        t = l;
    } else {
        merge(treap_pool[r].left_idx, l, treap_pool[r].left_idx);
        t = r;
    }
    pull_treap(t);
}

// Update point (col) in Treap with value K
void treap_update(int &root, int col, ll K) {
    int t1 = 0, t2 = 0, t3 = 0;
    split(root, col, t1, t2);       // t1: <= col
    split(t1, col - 1, t1, t3);     // t1: < col, t3: == col
    
    // t3 is the node with 'col' if it exists. 
    // We replace it or create a new one.
    // Note: We don't reuse the memory of t3 to keep it simple, 
    // or we can reuse t3 if it exists. Let's make a new node or update.
    if (t3 != 0) {
        treap_pool[t3].val = K;
        treap_pool[t3].gcd_val = K; 
        // Re-pulling isn't strictly needed as it has no children after split, 
        // but let's be safe.
        pull_treap(t3); 
    } else {
        t3 = new_treap_node(col, K);
    }
    
    merge(t1, t1, t3);
    merge(root, t1, t2);
}

// Query range [L, R] in Treap
ll treap_query(int root, int L, int R) {
    int t1 = 0, t2 = 0, t3 = 0;
    // Split into: < L, [L, R], > R
    split(root, R, t1, t2); // t1 <= R, t2 > R
    split(t1, L - 1, t1, t3); // t1 < L, t3 is range [L, R]
    
    ll res = get_treap_gcd(t3);
    
    // Merge back to restore structure
    merge(t1, t1, t3);
    merge(root, t1, t2);
    
    return res;
}

// ---------------------------------------------------------
// OUTER DATA STRUCTURE: SEGMENT TREE (Handles Rows)
// ---------------------------------------------------------
struct SegNode {
    int left_child;
    int right_child;
    int treap_root;
};

const int MAX_SEG_NODES = 800000; // Nu * log(R) approx
SegNode seg_pool[MAX_SEG_NODES];
int seg_ptr = 1;

int get_seg_node() {
    int idx = seg_ptr++;
    seg_pool[idx].left_child = 0;
    seg_pool[idx].right_child = 0;
    seg_pool[idx].treap_root = 0;
    return idx;
}

int root_seg = 0;
int ROWS, COLS;

// Get value of a specific column from a SegNode's treap
// We treat this as a range query [col, col]
ll get_val_at_col(int seg_idx, int col) {
    if (seg_idx == 0) return 0;
    return treap_query(seg_pool[seg_idx].treap_root, col, col);
}

void update_seg(int &node, int r_start, int r_end, int P, int Q, ll K) {
    if (node == 0) node = get_seg_node();
    
    // 1. If leaf row, update simple value
    if (r_start == r_end) {
        treap_update(seg_pool[node].treap_root, Q, K);
        return;
    }
    
    int mid = r_start + (r_end - r_start) / 2;
    if (P <= mid) {
        update_seg(seg_pool[node].left_child, r_start, mid, P, Q, K);
    } else {
        update_seg(seg_pool[node].right_child, mid + 1, r_end, P, Q, K);
    }
    
    // 2. Internal node: Update its Treap based on children
    ll val_left = get_val_at_col(seg_pool[node].left_child, Q);
    ll val_right = get_val_at_col(seg_pool[node].right_child, Q);
    ll new_val = gcd2(val_left, val_right);
    
    treap_update(seg_pool[node].treap_root, Q, new_val);
}

ll query_seg(int node, int r_start, int r_end, int P, int Q, int U, int V) {
    if (node == 0 || r_start > U || r_end < P) return 0;
    
    // If fully contained in row range, query the Treap for column range
    if (P <= r_start && r_end <= U) {
        return treap_query(seg_pool[node].treap_root, Q, V);
    }
    
    int mid = r_start + (r_end - r_start) / 2;
    return gcd2(query_seg(seg_pool[node].left_child, r_start, mid, P, Q, U, V),
                query_seg(seg_pool[node].right_child, mid + 1, r_end, P, Q, U, V));
}

// ---------------------------------------------------------
// INTERFACE IMPLEMENTATION
// ---------------------------------------------------------

void init(int R, int C) {
    ROWS = R;
    COLS = C;
    treap_ptr = 1;
    seg_ptr = 1;
    root_seg = 0;
    srand(2013); // Fixed seed for reproducibility
}

void update(int P, int Q, long long K) {
    // Limits: P is row 0..R-1, Q is col 0..C-1
    update_seg(root_seg, 0, ROWS - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query_seg(root_seg, 0, ROWS - 1, P, Q, U, V);
}

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