Submission #1306966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306966		orzorzorz	Game (IOI13_game)	C++20	63 / 100	1169 ms	279160 KiB

game

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

using namespace std;

typedef long long ll;

// 正確的 GCD 處理，確保包含 0 的情況
ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

struct nodey {
    nodey *l, *r;
    ll val;
    nodey() : l(nullptr), r(nullptr), val(0) {}
};

struct nodex {
    nodex *l, *r;
    nodey *nd;
    nodex() : l(nullptr), r(nullptr), nd(nullptr) {}
};

nodex *rt = nullptr;
int maxR, maxC;

// 更新內層 Y 軸
void updy(nodey *&idx, int q, ll val, int ql, int qr) {
    if (!idx) idx = new nodey();
    if (ql == qr) {
        idx->val = val;
        return;
    }
    int mid = ql + (qr - ql) / 2;
    if (q <= mid) updy(idx->l, q, val, ql, mid);
    else updy(idx->r, q, val, mid + 1, qr);
    
    ll v1 = idx->l ? idx->l->val : 0;
    ll v2 = idx->r ? idx->r->val : 0;
    idx->val = gcd(v1, v2);
}

// 專門用於獲取特定點的 GCD 值
ll get_valy(nodey *idx, int q, int ql, int qr) {
    if (!idx) return 0;
    if (ql == qr) return idx->val;
    int mid = ql + (qr - ql) / 2;
    if (q <= mid) return get_valy(idx->l, q, ql, mid);
    else return get_valy(idx->r, q, mid + 1, qr);
}

void updx(nodex *&idx, int p, int q, ll val, int ql, int qr) {
    if (!idx) idx = new nodex();
    
    if (ql == qr) {
        // 如果是 X 軸的葉子（代表某一行），直接更新該行的 Y 軸樹
        updy(idx->nd, q, val, 0, maxC - 1);
        return;
    }
    
    int mid = ql + (qr - ql) / 2;
    if (p <= mid) updx(idx->l, p, q, val, ql, mid);
    else updx(idx->r, p, q, val, mid + 1, qr);
    
    // 非葉子節點：當前位置的 GCD = 左子樹位置與右子樹位置的 GCD
    ll v1 = idx->l ? get_valy(idx->l->nd, q, 0, maxC - 1) : 0;
    ll v2 = idx->r ? get_valy(idx->r->nd, q, 0, maxC - 1) : 0;
    updy(idx->nd, q, gcd(v1, v2), 0, maxC - 1);
}

ll qryy(nodey *idx, int u, int v, int ql, int qr) {
    if (!idx || ql > v || qr < u) return 0;
    if (u <= ql && qr <= v) return idx->val;
    int mid = ql + (qr - ql) / 2;
    return gcd(qryy(idx->l, u, v, ql, mid), qryy(idx->r, u, v, mid + 1, qr));
}

ll qryx(nodex *idx, int p, int q, int u, int v, int ql, int qr) {
    if (!idx || ql > q || qr < p) return 0;
    if (p <= ql && qr <= q) return qryy(idx->nd, u, v, 0, maxC - 1);
    int mid = ql + (qr - ql) / 2;
    return gcd(qryx(idx->l, p, q, u, v, ql, mid), qryx(idx->r, p, q, u, v, mid + 1, qr));
}

void init(int R, int C) {
    maxR = R; maxC = C;
    rt = nullptr; // 重置樹
}

void update(int P, int Q, ll K) {
    updx(rt, P, Q, K, 0, maxR - 1);
}

ll calculate(int P, int Q, int U, int V) {
    // 修正點 1: 確保查詢區間 P <= U 且 Q <= V
    int r1 = min(P, U), r2 = max(P, U);
    int c1 = min(Q, V), c2 = max(Q, V);
    // 修正點 2: 傳遞正確的軸範圍給 qryx
    // qryx(root, X_start, X_end, Y_start, Y_end, root_X_L, root_X_R)
    return qryx(rt, r1, r2, c1, c2, 0, maxR - 1);
}

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