Submission #1246594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246594		aykhn	Game (IOI13_game)	C++20	0 / 100	0 ms	328 KiB

game

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

// Implicit 2D segment tree using index-based pools to reduce memory
// Each node stores children as int indices into a vector, not pointers.

struct NodeY {
    int l = 0, r = 0;   // child indices (0 means null)
    int val = 0;        // value stored (int is enough if |K| <= 1e9)
};

struct NodeX {
    int l = 0, r = 0;   // child indices in poolX
    int rtY = 0;        // root index in poolY
};

static vector<NodeY> poolY(1); // index 0 = null
static vector<NodeX> poolX(1); // index 0 = null

inline int newY() {
    poolY.push_back(NodeY());
    return (int)poolY.size() - 1;
}

inline int newX() {
    poolX.push_back(NodeX());
    return (int)poolX.size() - 1;
}

int n, m;
int root = 0;

// Merge two Y-trees over [ly, ry]
int mergeY(int a, int b, int ly, int ry) {
    if (!a && !b) return 0;
    int idx = newY();
    if (ly == ry) {
        int va = a ? poolY[a].val : 0;
        int vb = b ? poolY[b].val : 0;
        poolY[idx].val = std::gcd(va, vb);
        return idx;
    }
    int my = (ly + ry) >> 1;
    poolY[idx].l = mergeY(a ? poolY[a].l : 0, b ? poolY[b].l : 0, ly, my);
    poolY[idx].r = mergeY(a ? poolY[a].r : 0, b ? poolY[b].r : 0, my+1, ry);
    int vl = poolY[idx].l ? poolY[ poolY[idx].l ].val : 0;
    int vr = poolY[idx].r ? poolY[ poolY[idx].r ].val : 0;
    poolY[idx].val = std::gcd(vl, vr);
    return idx;
}

// Point-set update on single Y-tree
void updateY(int &node, int ly, int ry, int y, int v) {
    if (!node) node = newY();
    if (ly == ry) {
        poolY[node].val = v;
        return;
    }
    int my = (ly + ry) >> 1;
    if (y <= my) updateY(poolY[node].l, ly, my, y, v);
    else          updateY(poolY[node].r, my+1, ry, y, v);
    int vl = poolY[node].l ? poolY[ poolY[node].l ].val : 0;
    int vr = poolY[node].r ? poolY[ poolY[node].r ].val : 0;
    poolY[node].val = std::gcd(vl, vr);
}

// Update X-tree: set a[x][y] = v
void updateX(int &node, int lx, int rx, int x, int y, int v) {
    if (!node) node = newX();
    if (lx == rx) {
        updateY(poolX[node].rtY, 0, m-1, y, v);
        return;
    }
    int mx = (lx + rx) >> 1;
    if (x <= mx) updateX(poolX[node].l, lx, mx, x, y, v);
    else          updateX(poolX[node].r, mx+1, rx, x, y, v);
    // merge child Y-trees
    int leftY  = poolX[ poolX[node].l ].rtY;
    int rightY = poolX[ poolX[node].r ].rtY;
    poolX[node].rtY = mergeY(leftY, rightY, 0, m-1);
}

// GCD query on one Y-tree
int queryY(int node, int ly, int ry, int y1, int y2) {
    if (!node || ry < y1 || ly > y2) return 0;
    if (y1 <= ly && ry <= y2) return poolY[node].val;
    int my = (ly + ry) >> 1;
    return std::gcd(
        queryY(poolY[node].l, ly, my, y1, y2),
        queryY(poolY[node].r, my+1, ry, y1, y2)
    );
}

// Submatrix GCD query
int queryX(int 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) {
        return queryY(poolX[node].rtY, 0, m-1, y1, y2);
    }
    int mx = (lx + rx) >> 1;
    return std::gcd(
        queryX(poolX[node].l, lx, mx, x1, x2, y1, y2),
        queryX(poolX[node].r, mx+1, rx, x1, x2, y1, y2)
    );
}

// game.h interface
void init(int R, int C) {
    n = R; m = C;
    poolY.clear(); poolY.resize(1);
    poolX.clear(); poolX.resize(1);
    root = 0;
}

void update(int P, int Q, long long K) {
    // cast K to int if within bounds
    updateX(root, 0, n-1, P, Q, (int)K);
}

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

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