Submission #1246584

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

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int MXN = 2e3 + 5;

struct NodeY {
  long long val = 0;
  NodeY *left = nullptr, *right = nullptr;
};

struct NodeX {
    NodeX *left = nullptr, *right = nullptr;
    NodeY *treeY = nullptr;
  };
  
int n, m;
// Update Y-axis segment tree
void updateY(NodeY* &node, int ly, int ry, int y, long long val) {
    if (!node) node = new NodeY();
    if (ly == ry) {
        node->val = val;
        return;
    }
    int my = (ly + ry) / 2;
    if (y <= my) updateY(node->left, ly, my, y, val);
    else updateY(node->right, my + 1, ry, y, val);

    long long lv = node->left ? node->left->val : 0;
    long long rv = node->right ? node->right->val : 0;
    node->val = gcd(lv, rv);
}

// Update X-axis tree, propagating to Y
void updateX(NodeX* &node, int lx, int rx, int x, int y, long long val) {
    if (!node) node = new NodeX();
    updateY(node->treeY, 0, m - 1, y, val);

    if (lx == rx) return;
    int mx = (lx + rx) / 2;
    if (x <= mx) updateX(node->left, lx, mx, x, y, val);
    else updateX(node->right, mx + 1, rx, x, y, val);
}

// Query 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) / 2;
    return gcd(
        queryY(node->left, ly, my, y1, y2),
        queryY(node->right, my + 1, ry, y1, y2)
    );
}

// Query X-tree
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) return queryY(node->treeY, 0, m - 1, y1, y2);
    int mx = (lx + rx) / 2;
    return gcd(
        queryX(node->left, lx, mx, x1, x2, y1, y2),
        queryX(node->right, mx + 1, rx, x1, x2, y1, y2)
    );
}

NodeX *root = nullptr;

void init(int R, int C) {
  n = R, m = C;
}

void update(int P, int Q, long long K) {
  updateX(root, 0, n - 1, P, Q, 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