Submission #1008278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008278		jakobrs	Game (IOI13_game)	C++17	0 / 100	2 ms	860 KiB

game

#include "game.h"

#include <csignal>
#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 Node1 {
  Node1 *l, *r;
  i32 from, to;
  i64 val;

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

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

  auto left() -> Node1 * { return l ?: l = new Node1(from, midpoint(from, to)); }
  auto right() -> Node1 * { return r ?: r = new Node1(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));
    }
  }
};

struct Node2 {
  Node2 *l, *r;
  i32 from, to;
  Node1 *val;
  i32 width;

  explicit Node2(i32 from, i32 to, i32 width)
      : l{nullptr}, r{nullptr}, from{from}, to{to}, val{new Node1{width}},
        width{width} {}

  explicit Node2(i32 len, i32 width) : Node2(0, len, width) {}

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

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

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

      // Have to fix value for column c
      auto fixed = 0;
      if (l)
        fixed = std::gcd(fixed, l->val->query(C, C + 1));
      if (r)
        fixed = std::gcd(fixed, r->val->query(C, C + 1));
      val->set(C, fixed);
    } else {
      val->set(C, i);
    }
  }

  auto query(i32 x1, i32 x2, i32 y1, i32 y2) -> i64 {
    if (x1 <= from && to <= x2) {
      return val->query(y1, y2);
    } else if (to <= x1 || x2 <= from) {
      return 0;
    } else {
      return std::gcd(left()->query(x1, x2, y1, y2),
                      right()->query(x1, x2, y1, y2));
    }
  }
};

namespace {
Node2 *st;

i32 h, w;
} // namespace

void init(i32 R, i32 C) {
  st = new Node2{R, C};

  h = R;
  w = C;
}

void update(i32 P, i32 Q, i64 K) { st->set(P, Q, K); }

auto calculate(i32 P, i32 Q, i32 U, i32 V) -> i64 {
  return st->query(P, U + 1, Q, V + 1);
}

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