Submission #1008180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008180		jakobrs	Game (IOI13_game)	C++17	37 / 100	13042 ms	89104 KiB

game

#include "game.h"

#include <iostream>
#include <numeric>
#include <vector>

using i32 = int32_t;
using i64 = long long;

auto midpoint(i32 l, i32 r) -> i32 { return l + (r - l) / 2; }

struct Node {
  Node *l, *r;
  i32 from, to;
  i64 val;

  explicit Node(i32 from, i32 to)
      : l{nullptr}, r{nullptr}, from{from}, to{to}, val{0} {}

  explicit Node(i32 len) : Node(0, len) {}

  auto left() -> Node * { return l ?: l = new Node(from, midpoint(from, to)); }
  auto right() -> Node * { return r ?: r = new Node(midpoint(from, to), to); }

  void set(i32 pos, i64 i) {
    if (to - from > 1) {
      auto m = midpoint(from, to);

      if (pos < m)
        left()->set(pos, i);
      else
        right()->set(pos, i);

      val = 0;
      if (l)
        val = std::gcd(val, l->val);
      if (r)
        val = std::gcd(val, r->val);
    } else {
      val = i;
    }
  }

  auto query(i32 l, i32 r) -> i64 {
    if (l <= from && to <= r) {
      // std::cerr << "including " << from << ".." << to << "\n";
      return val;
    } else if (to <= l || r <= from) {
      // std::cerr << "excluding " << from << ".." << to << "\n";
      return 0;
    } else {
      return std::gcd(left()->query(l, r), right()->query(l, r));
    }
  }
};

namespace {
std::vector<Node> rows;

i32 h, w;
} // namespace

void init(i32 R, i32 C) {
  rows.reserve(R);
  for (i32 i = 0; i < R; i++)
    rows.emplace_back(C);

  h = R;
  w = C;
}

void update(i32 P, i32 Q, i64 K) {
  // std::cerr << "Setting " << P << " " << Q << " to " << K << "\n";
  rows[P].set(Q, K);
}

auto calculate(i32 P, i32 Q, i32 U, i32 V) -> i64 {
  // std::cerr << "range: " << P << ' ' << Q << ' ' << U << ' ' << V << '\n';
  i64 val = 0;
  for (i32 r = P; r <= U; r++) {
    // std::cerr << "row " << r << " res " << rows[r].query(Q, V + 1) << '\n';
    val = std::gcd(val, rows[r].query(Q, V + 1));
  }
  return val;
}

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