Submission #1306874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306874		orzorzorz	게임 (IOI13_game)	C++20	80 / 100	3774 ms	239548 KiB

game

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

using namespace std;

typedef long long ll;

// 題目提供的 GCD 函數
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;
}

// ---------------------------------------------------------
// 內層線段樹 (Y軸 - 列 Columns)
// ---------------------------------------------------------
struct NodeY {
    int left_child;
    int right_child;
    ll val; // 儲存區間 GCD
};

// 記憶體池：內層節點數量龐大，需要開大一點
const int MAX_NODES_Y = 250000*60; 
NodeY treeY[MAX_NODES_Y];
int ptrY = 1; // 0 保留給空節點 (NULL)

int get_nodeY() {
    return ptrY++;
}

// 內層：更新位置 pos 的值為 k
void updateY(int &node, int l, int r, int pos, ll k) {
    if (!node) node = get_nodeY();
    
    if (l == r) {
        treeY[node].val = k;
        return;
    }
    
    int mid = l + (r - l) / 2;
    if (pos <= mid) updateY(treeY[node].left_child, l, mid, pos, k);
    else updateY(treeY[node].right_child, mid + 1, r, pos, k);
    
    treeY[node].val = gcd2(treeY[treeY[node].left_child].val, 
                           treeY[treeY[node].right_child].val);
}

// 內層：查詢區間 [ql, qr] 的 GCD
ll queryY(int node, int l, int r, int ql, int qr) {
    if (!node || l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return treeY[node].val;
    
    int mid = l + (r - l) / 2;
    return gcd2(queryY(treeY[node].left_child, l, mid, ql, qr),
                queryY(treeY[node].right_child, mid + 1, r, ql, qr));
}

// ---------------------------------------------------------
// 外層線段樹 (X軸 - 行 Rows)
// ---------------------------------------------------------
struct NodeX {
    int left_child;
    int right_child;
    int rootY; // 指向內層線段樹的根
};

// 外層節點數量較少 (N_U * log R)
const int MAX_NODES_X = 700000; 
NodeX treeX[MAX_NODES_X];
int ptrX = 1;
int rootX = 0;

int R_MAX, C_MAX;

// 輔助：從某個內層樹查詢單點 val (用來合併外層節點)
ll get_val_at_col(int inner_root, int col) {
    return queryY(inner_root, 0, C_MAX - 1, col, col);
}

// 外層：更新 (P, Q) 為 K
void updateX(int &node, int l, int r, int P, int Q, ll K) {
    if (!node) {
        node = ptrX++;
        treeX[node].rootY = 0; // 初始內層樹為空
    }
    
    // 1. 如果是葉子節點 (特定的行 P)
    if (l == r) {
        // 直接在內層樹更新列 Q
        updateY(treeX[node].rootY, 0, C_MAX - 1, Q, K);
        return;
    }
    
    int mid = l + (r - l) / 2;
    if (P <= mid) updateX(treeX[node].left_child, l, mid, P, Q, K);
    else updateX(treeX[node].right_child, mid + 1, r, P, Q, K);
    
    // 2. 如果是內部節點 (行區間)
    // 我們需要在這個節點的「內層樹」中，更新列 Q 的值。
    // 這個值應該是：GCD(左子樹在Q的值, 右子樹在Q的值)
    
    ll val_left = 0, val_right = 0;
    if (treeX[node].left_child) 
        val_left = get_val_at_col(treeX[treeX[node].left_child].rootY, Q);
    
    if (treeX[node].right_child)
        val_right = get_val_at_col(treeX[treeX[node].right_child].rootY, Q);
        
    ll new_gcd = gcd2(val_left, val_right);
    
    // 更新當前外層節點的內層樹
    updateY(treeX[node].rootY, 0, C_MAX - 1, Q, new_gcd);
}

// 外層：查詢矩形
ll queryX(int node, int l, int r, int P, int Q, int U, int V) {
    if (!node || l > U || r < P) return 0;
    
    // 如果行範圍完全被包含
    if (P <= l && r <= U) {
        // 直接查詢該節點的內層樹 (列範圍 Q~V)
        return queryY(treeX[node].rootY, 0, C_MAX - 1, Q, V);
    }
    
    int mid = l + (r - l) / 2;
    return gcd2(queryX(treeX[node].left_child, l, mid, P, Q, U, V),
                queryX(treeX[node].right_child, mid + 1, r, P, Q, U, V));
}

// ---------------------------------------------------------
// 介面實作
// ---------------------------------------------------------

void init(int R, int C) {
    R_MAX = R;
    C_MAX = C;
    ptrX = 1;
    ptrY = 1;
    rootX = 0;
}

void update(int P, int Q, long long K) {
    updateX(rootX, 0, R_MAX - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return queryX(rootX, 0, R_MAX - 1, P, Q, U, V);
}

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