Submission #1246587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246587		aykhn	Game (IOI13_game)	C++20	10 / 100	448 ms	321536 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

// We’ll use std::gcd on long long
// (C++17 <numeric> is included via <bits/stdc++.h>)

struct NodeY {
    long long val = 0;
    NodeY *l = nullptr, *r = nullptr;
};

struct NodeX {
    NodeX *l = nullptr, *r = nullptr;
    NodeY *treeY = nullptr;
};

int n, m;
NodeX* root = nullptr;

// Merge two Y‑trees over [ly, ry], return a newly built tree
NodeY* mergeY(NodeY* A, NodeY* B, int ly, int ry) {
    if (!A && !B) return nullptr;
    NodeY* node = new NodeY();
    if (ly == ry) {
        long long va = A ? A->val : 0;
        long long vb = B ? B->val : 0;
        node->val = std::gcd(va, vb);
        return node;
    }
    int my = (ly + ry) >> 1;
    node->l = mergeY(A ? A->l : nullptr, B ? B->l : nullptr, ly, my);
    node->r = mergeY(A ? A->r : nullptr, B ? B->r : nullptr, my+1, ry);
    long long vl = node->l ? node->l->val : 0;
    long long vr = node->r ? node->r->val : 0;
    node->val = std::gcd(vl, vr);
    return node;
}

// Point‐set update on Y‑tree at fixed X‑node
void updateY(NodeY*& node, int ly, int ry, int y, long long v) {
    if (!node) node = new NodeY();
    if (ly == ry) {
        node->val = v;
        return;
    }
    int my = (ly + ry) >> 1;
    if (y <= my) updateY(node->l, ly, my, y, v);
    else          updateY(node->r, my+1, ry, y, v);
    long long vl = node->l ? node->l->val : 0;
    long long vr = node->r ? node->r->val : 0;
    node->val = std::gcd(vl, vr);
}

// Update X‑tree: set a[x][y]=v
void updateX(NodeX*& node, int lx, int rx, int x, int y, long long v) {
    if (!node) node = new NodeX();
    if (lx == rx) {
        // leaf in X: just update its Y‑tree
        updateY(node->treeY, 0, m-1, y, v);
        return;
    }
    int mx = (lx + rx) >> 1;
    if (x <= mx) updateX(node->l, lx, mx, x, y, v);
    else         updateX(node->r, mx+1, rx, x, y, v);
    // after children are updated, merge their Y‑trees
    node->treeY = mergeY(
        node->l ? node->l->treeY : nullptr,
        node->r ? node->r->treeY : nullptr,
        0, m-1
    );
}

// GCD query on a single Y‑tree
long long queryY(NodeY* node, int ly, int ry, int y1, int y2) {
    if (!node || ry < y1 || ly > y2) return 0;
    if (y1 <= ly && ry <= y2) return node->val;
    int my = (ly + ry) >> 1;
    return std::gcd(
        queryY(node->l, ly, my, y1, y2),
        queryY(node->r, my+1, ry, y1, y2)
    );
}

// Submatrix GCD query on [x1,x2]×[y1,y2]
long long queryX(NodeX* node, int lx, int rx,
                 int x1, int x2, int y1, int y2) {
    if (!node || rx < x1 || lx > x2) return 0;
    if (x1 <= lx && rx <= x2) {
        // fully covered in X → query its Y‑tree
        return queryY(node->treeY, 0, m-1, y1, y2);
    }
    int mx = (lx + rx) >> 1;
    return std::gcd(
        queryX(node->l, lx, mx, x1, x2, y1, y2),
        queryX(node->r, mx+1, rx, x1, x2, y1, y2)
    );
}

// game.h interface
void init(int R, int C) {
    n = R;
    m = C;
    root = nullptr;
}

void update(int P, int Q, long long K) {
    // set a[P][Q] = K
    updateX(root, 0, n-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    // query GCD on [P..U]×[Q..V]
    return queryX(root, 0, n-1, P, U, Q, V);
}

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