oj.uz

Submission #1008180

# Submission time Handle Problem Language Result Execution time Memory
1008180 2024-06-26T08:11:28 Z jakobrs Game (IOI13_game) C++17
37 / 100
 13000 ms 89104 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 616 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 829 ms 28280 KB Output is correct
5 Correct 408 ms 12264 KB Output is correct
6 Correct 956 ms 87588 KB Output is correct
7 Correct 1033 ms 87304 KB Output is correct
8 Correct 894 ms 89104 KB Output is correct
9 Correct 946 ms 88276 KB Output is correct
10 Correct 838 ms 87120 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 948 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Execution timed out 13018 ms 18288 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 432 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 688 ms 28360 KB Output is correct
13 Correct 329 ms 12392 KB Output is correct
14 Correct 801 ms 87636 KB Output is correct
15 Correct 811 ms 87376 KB Output is correct
16 Correct 708 ms 88976 KB Output is correct
17 Correct 832 ms 88388 KB Output is correct
18 Correct 788 ms 87124 KB Output is correct
19 Execution timed out 13027 ms 18680 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 758 ms 28384 KB Output is correct
13 Correct 331 ms 12320 KB Output is correct
14 Correct 857 ms 87636 KB Output is correct
15 Correct 876 ms 87384 KB Output is correct
16 Correct 752 ms 88920 KB Output is correct
17 Correct 827 ms 88412 KB Output is correct
18 Correct 761 ms 87216 KB Output is correct
19 Execution timed out 13042 ms 18256 KB Time limit exceeded
20 Halted 0 ms 0 KB -