Submission #1306965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306965		orzorzorz	Game (IOI13_game)	C++20	0 / 100	2 ms	584 KiB

game

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

using namespace std;

typedef long long ll;

// 標準 GCD 函數
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 軸線段樹
// mode = 0: 直接更新 leaf 的值 (外層是 leaf)
// mode = 1: 取左右子樹的 GCD (外層是非 leaf)
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);
}

// 獲取內層樹特定位置的值，用於外層非葉子節點的合併
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);
}

// 更新外層 X 軸線段樹
void updx(nodex *&idx, int p, int q, ll val, int ql, int qr) {
    if (!idx) idx = new nodex();
    
    if (ql == qr) {
        // 外層葉子：直接更新內層
        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);
    
    // 非葉子節點：內層位置 Q 的值 = gcd(左子樹位置 Q, 右子樹位置 Q)
    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);
}

// 查詢內層 Y 軸
ll qryy(nodey *idx, int u, int v, int ql, int qr) {
    if (!idx || u > qr || v < ql) 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));
}

// 查詢外層 X 軸
ll qryx(nodex *idx, int p, int q, int u, int v, int ql, int qr) {
    if (!idx || p > qr || q < ql) 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) {
    return qryx(rt, P, Q, U, V, 0, maxR - 1);
}

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