Submission #645601

#	Time	Username	Problem	Language	Result	Execution time	Memory
645601		abeker	Game (IOI13_game)	C++17	63 / 100	2070 ms	256000 KiB

game

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

typedef long long ll;

const int offset = 1 << 30;

struct ColumnNode {
  ll num;
  ColumnNode *l, *r;
  ColumnNode() : num(0), l(nullptr), r(nullptr) {}
};

struct RowNode {
  ColumnNode* root;
  RowNode *l, *r;
  RowNode() : root(new ColumnNode()), l(nullptr), r(nullptr) {}
};

ll gcd(ll a, ll b) {
  return b ? gcd(b, a % b) : a;
}

RowNode* row_root;

void init(int R, int C) {
  row_root = new RowNode();
}

ColumnNode* get_left(ColumnNode* x) {
  return x ? x -> l : nullptr;
}

ColumnNode* get_right(ColumnNode* x) {
  return x ? x -> r : nullptr;
}

ll get_num(ColumnNode* x) {
  return x ? x -> num : 0;
}

void update_col(ColumnNode *x, int lo, int hi, ColumnNode* lft, ColumnNode* rig, int col, ll val) {
  if (hi - lo == 1) {
    x -> num = lft || rig ? gcd(get_num(lft), get_num(rig)) : val;
    return;
  }
  int mid = (lo + hi) / 2;
  if (col < mid) {
    if (!(x -> l))
      x -> l = new ColumnNode();
    update_col(x -> l, lo, mid, get_left(lft), get_left(rig), col, val);
  }
  else {
    if (!(x -> r))
      x -> r = new ColumnNode();
    update_col(x -> r, mid, hi, get_right(lft), get_right(rig), col, val);
  }
  x -> num = gcd(get_num(x -> l), get_num(x -> r));
}

ColumnNode* get_root(RowNode* x) {
  return x ? x -> root : nullptr;
}

void update_row(RowNode* x, int lo, int hi, int row, int col, ll val) {
  if (hi - lo > 1) {
    int mid = (lo + hi) / 2;
    if (row < mid) {
      if (!(x -> l))
        x -> l = new RowNode();
      update_row(x -> l, lo, mid, row, col, val);
    }
    else {
      if (!(x -> r))
        x -> r = new RowNode();
      update_row(x -> r, mid, hi, row, col, val);
    }
  }
  update_col(x -> root, 0, offset, get_root(x -> l), get_root(x -> r), col, val);
}

void update(int p, int q, ll k) {
  update_row(row_root, 0, offset, p, q, k);
}

ll query_col(ColumnNode* x, int lo, int hi, int from, int to) {
  if (!x || lo >= to || hi <= from)
    return 0;
  if (lo >= from && hi <= to)
    return x -> num;
  int mid = (lo + hi) / 2;
  return gcd(query_col(x -> l, lo, mid, from, to), query_col(x -> r, mid, hi, from, to));
}

ll query_row(RowNode* x, int lo, int hi, int from, int to, int col1, int col2) {
  if (!x || lo >= to || hi <= from)
    return 0;
  if (lo >= from && hi <= to)
    return query_col(x -> root, 0, offset, col1, col2);
  int mid = (lo + hi) / 2;
  return gcd(query_row(x -> l, lo, mid, from, to, col1, col2), query_row(x -> r, mid, hi, from, to, col1, col2));
}

ll calculate(int p, int q, int u, int v) {
  return query_row(row_root, 0, offset, p, u + 1, q, v + 1);
}

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