Submission #1306871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306871		orzorzorz	게임 (IOI13_game)	C++20	100 / 100	4024 ms	29148 KiB

game

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

using namespace std;

typedef long long ll;

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)
// ---------------------------------------------------------
// 節點大小嚴格控制在 16 Bytes
struct NodeY {
    int l;      // 若是內部節點：左子樹索引；若是葉子：儲存列座標 (Key)
    int r;      // 若是內部節點：右子樹索引；若是葉子：標記為 -1
    ll val;     // GCD 數值
};

// 記憶體池：開 1300 萬個節點 (約 200 MB)
// Subtask 5 極限約需 1.2e7 節點
const int MAX_NODES_Y = 13000000; 
NodeY treeY[MAX_NODES_Y];
int ptrY = 1;

int new_nodeY() {
    return ptrY++;
}

// 內層更新：支援葉節點優化
void updateY(int &node, int l, int r, int pos, ll k) {
    if (!node) {
        // 情況 1: 空節點，直接建立葉子
        node = new_nodeY();
        treeY[node].l = pos; // 借用 l 存座標
        treeY[node].r = -1;  // 標記為葉子
        treeY[node].val = k;
        return;
    }

    // 情況 2: 當前是葉子節點
    if (treeY[node].r == -1) {
        // 如果座標相同，直接更新數值
        if (treeY[node].l == pos) {
            treeY[node].val = k;
            return;
        }
        
        // 座標不同（衝突），必須分裂成內部節點
        int old_pos = treeY[node].l;
        ll old_val = treeY[node].val;
        
        // 轉為內部節點 (重置左右子樹)
        treeY[node].l = 0;
        treeY[node].r = 0;
        treeY[node].val = gcd2(old_val, k); // 先預存 GCD
        
        // 遞迴插入舊的值與新的值
        // 注意：這裡直接呼叫遞迴，讓系統自動分配到正確的子層
        updateY(node, l, r, old_pos, old_val);
        updateY(node, l, r, pos, k);
        return;
    }

    // 情況 3: 內部節點，標準線段樹遞迴
    int mid = l + (r - l) / 2;
    if (pos <= mid) updateY(treeY[node].l, l, mid, pos, k);
    else updateY(treeY[node].r, mid + 1, r, pos, k);

    // Pull: 更新 GCD
    ll val_l = treeY[node].l ? treeY[treeY[node].l].val : 0;
    ll val_r = treeY[node].r ? treeY[treeY[node].r].val : 0;
    treeY[node].val = gcd2(val_l, val_r);
}

// 內層查詢
ll queryY(int node, int l, int r, int ql, int qr) {
    if (!node || l > qr || r < ql) return 0;
    
    // 如果是葉子節點，檢查座標是否在範圍內
    if (treeY[node].r == -1) {
        int key = treeY[node].l;
        if (key >= ql && key <= qr) return treeY[node].val;
        return 0;
    }
    
    // 標準區間查詢
    if (ql <= l && r <= qr) return treeY[node].val;
    
    int mid = l + (r - l) / 2;
    return gcd2(queryY(treeY[node].l, l, mid, ql, qr),
                queryY(treeY[node].r, mid + 1, r, ql, qr));
}

// ---------------------------------------------------------
// 外層線段樹 (X軸 - Rows)
// ---------------------------------------------------------
struct NodeX {
    int l, r;
    int rootY; // 內層樹根
};

// 外層節點數較少 (22000 * 30 ~ 660,000)
const int MAX_NODES_X = 700000;
NodeX treeX[MAX_NODES_X];
int ptrX = 1;
int rootX = 0;

int R_MAX, C_MAX;

// 輔助：從內層樹取得單點的值 (用於外層合併)
ll get_val_at(int inner_root, int col) {
    // 利用 queryY 查詢單點 [col, col]
    return queryY(inner_root, 0, C_MAX - 1, col, col);
}

void updateX(int &node, int l, int r, int P, int Q, ll K) {
    if (!node) node = ptrX++;
    
    // 1. 葉子行 (Row P)
    if (l == r) {
        updateY(treeX[node].rootY, 0, C_MAX - 1, Q, K);
        return;
    }
    
    int mid = l + (r - l) / 2;
    if (P <= mid) updateX(treeX[node].l, l, mid, P, Q, K);
    else updateX(treeX[node].r, mid + 1, r, P, Q, K);
    
    // 2. 內部行：計算新的 GCD 並更新到內層樹
    // 這裡我們需要知道左子樹和右子樹在 (P, Q) 處的值
    // 注意：只更新列 Q，因為只有這個位置變了
    ll val_l = treeX[node].l ? get_val_at(treeX[treeX[node].l].rootY, Q) : 0;
    ll val_r = treeX[node].r ? get_val_at(treeX[treeX[node].r].rootY, Q) : 0;
    
    updateY(treeX[node].rootY, 0, C_MAX - 1, Q, gcd2(val_l, val_r));
}

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) {
        return queryY(treeX[node].rootY, 0, C_MAX - 1, Q, V);
    }
    
    int mid = l + (r - l) / 2;
    return gcd2(queryX(treeX[node].l, l, mid, P, Q, U, V),
                queryX(treeX[node].r, 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: 20 / 20