#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));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
351 ms |
12044 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
180 ms |
17244 KB |
Output is correct |
| 3 |
Correct |
352 ms |
71444 KB |
Output is correct |
| 4 |
Correct |
558 ms |
56668 KB |
Output is correct |
| 5 |
Correct |
485 ms |
55900 KB |
Output is correct |
| 6 |
Incorrect |
136 ms |
12512 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
