Submission #255574

#	Time	Username	Problem	Language	Result	Execution time	Memory
255574		EntityIT	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	558 ms	71444 KiB

rainbow

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

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

#include "rainbow.h"

template<class X, class Y, class T>
struct BIT2D {
  vec<X, 1> compressed_xs;
  vec<Y, 2> compressed_ys_groups;
  vec<T, 2> a;
  BIT2D(const vec<pair<X, Y>, 1>& points = vec<pair<X, Y>, 1>()) {
    for (auto& point : points) {
      compressed_xs.emplace_back(point.first);
    }
    sort(ALL(compressed_xs)); compressed_xs.erase(unique(ALL(compressed_xs)), compressed_xs.end());
    compressed_ys_groups.resize(SZ(compressed_xs));
    for (auto& point : points) {
      for (int i = static_cast<int>(lower_bound(ALL(compressed_xs), point.first) - compressed_xs.begin()); i < SZ(compressed_xs); i |= i + 1) {
        compressed_ys_groups[i].emplace_back(point.second);
      }
    }
    for (auto& compressed_ys : compressed_ys_groups) {
      sort(ALL(compressed_ys)); compressed_ys.erase(unique(ALL(compressed_ys)), compressed_ys.end());
    }
    a = compressed_ys_groups;
    for (auto& i : a) {
      fill(ALL(i), T());
    }
  }

  template<class U>
  void Add(X x, Y y, U value) {
    for (int i = static_cast<int>(lower_bound(ALL(compressed_xs), x) - compressed_xs.begin()); i < SZ(compressed_xs); i |= i + 1) {
      for (int j = static_cast<int>(lower_bound(ALL(compressed_ys_groups[i]), y) - compressed_ys_groups[i].begin()); j < SZ(compressed_ys_groups[i]); j |= j + 1) {
        a[i][j] += value;
      }
    }
  }
  T Get(X x, Y y) const {
    T ret{};
    for (int i = static_cast<int>(upper_bound(ALL(compressed_xs), x) - compressed_xs.begin()) - 1; ~i; i = (i & (i + 1)) - 1) {
      for (int j = static_cast<int>(upper_bound(ALL(compressed_ys_groups[i]), y) - compressed_ys_groups[i].begin()) - 1; ~j; j = (j & (j + 1)) - 1) {
        ret += a[i][j];
      }
    }
    return ret;
  }
  T Get(X x_1, Y y_1, X x_2, Y y_2) const {
    return Get(x_2, y_2) + Get(x_1 - 1, y_1 - 1) - Get(x_2, y_1 - 1) - Get(x_1 - 1, y_2);
  }
};
BIT2D<int, int, int> bit2D_cell, bit2D_vertex, bit2D_vertical_edge, bit2D_horizontal_edge;

void init(int n_rows, int n_columns, int starting_row, int starting_column, int n_steps, char *steps) {
  vec<pair<int, int>, 1> cells, vertices, vertical_edges, horizontal_edges;
  for (int i = 0, x = starting_row, y = starting_column; i <= n_steps; x += steps[i] == 'N' ? -1 : (steps[i] == 'S' ? 1 : 0), y += steps[i] == 'W' ? -1 : (steps[i] == 'E' ? 1 : 0), ++i) {
    cells.emplace_back(x, y);
    vertices.emplace_back(x, y);
    vertices.emplace_back(x - 1, y);
    vertices.emplace_back(x, y - 1);
    vertices.emplace_back(x - 1, y - 1);
    vertical_edges.emplace_back(x, y);
    vertical_edges.emplace_back(x, y - 1);
    horizontal_edges.emplace_back(x, y);
    horizontal_edges.emplace_back(x - 1, y);
  }
  sort(ALL(cells)); cells.erase(unique(ALL(cells)), cells.end());
  sort(ALL(vertices)); vertices.erase(unique(ALL(vertices)), vertices.end());
  sort(ALL(vertical_edges)); vertical_edges.erase(unique(ALL(vertical_edges)), vertical_edges.end());
  sort(ALL(horizontal_edges)); horizontal_edges.erase(unique(ALL(horizontal_edges)), horizontal_edges.end());
  bit2D_cell = BIT2D<int, int, int>(cells);
  bit2D_vertex = BIT2D<int, int, int>(vertices);
  bit2D_vertical_edge = BIT2D<int, int, int>(vertical_edges);
  bit2D_horizontal_edge = BIT2D<int, int, int>(horizontal_edges);
  for (auto& cell : cells) {
    bit2D_cell.Add(cell.first, cell.second, 1);
  }
  for (auto& vertex : vertices) {
    bit2D_vertex.Add(vertex.first, vertex.second, 1);
  }
  for (auto& vertical_edge : vertical_edges) {
    bit2D_vertical_edge.Add(vertical_edge.first, vertical_edge.second, 1);
  }
  for (auto& horizontal_edge : horizontal_edges) {
    bit2D_horizontal_edge.Add(horizontal_edge.first, horizontal_edge.second, 1);
  }
}

int colour(int r_1, int c_1, int r_2, int c_2) {
  int n_vertices = ((r_2 - r_1 + 1 + c_2 - c_1 + 1) << 1) + bit2D_vertex.Get(r_1, c_1, r_2 - 1, c_2 - 1);

  int n_edges = ((r_2 - r_1 + 1 + c_2 - c_1 + 1) << 1) + bit2D_vertical_edge.Get(r_1, c_1, r_2, c_2 - 1) + bit2D_horizontal_edge.Get(r_1, c_1, r_2 - 1, c_2);

  int n_connected_components = 1 + (bit2D_vertex.Get(r_1 - 1, c_1 - 1, r_2, c_2) == bit2D_vertex.Get(r_1, c_1, r_2 - 1, c_2 - 1));

  return 1 + n_connected_components - n_vertices + n_edges - (1 + bit2D_cell.Get(r_1, c_1, r_2, c_2));
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26