Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
#include
#include
struct Vector3 { int x; int y; int z; bool operator !=(const Vector3& other) { return (x != other.x) && (y != other.y) && (z != other.z); } }; struct Cell { int value; Vector3 pos; }; using Tensor = std::vector
>>; using SparseTable = std::vector
>>; using SparseTable2d = std::vector
>; using Matrix = std::vector
>; Cell maxCell(const Cell& a, const Cell& b) { return (a.value >= b.value) ? a : b; } struct QueryResult { int value; Vector3 pos; }; QueryResult query_max(const SparseTable& table, Vector3 start, Vector3 size) { int x = start.x; int y = start.y; int z = start.z; int a = size.x; int b = size.y; int c = size.z; int x2 = x + a - 1; int y2 = y + b - 1; int z2 = z + c - 1; int logx = std::log2(a); int logy = std::log2(b); int logz = std::log2(c); int x_shift = (1 << logx); int y_shift = (1 << logy); int z_shift = (1 << logz); std::vector
cells = { table[x][y][z][logx][logy][logz], table[x2 - x_shift + 1][y][z][logx][logy][logz], table[x][y2 - y_shift + 1][z][logx][logy][logz], table[x][y][z2 - z_shift + 1][logx][logy][logz], table[x2 - x_shift + 1][y2 - y_shift + 1][z][logx][logy][logz], table[x2 - x_shift + 1][y][z2 - z_shift + 1][logx][logy][logz], table[x][y2 - y_shift + 1][z2 - z_shift + 1][logx][logy][logz], table[x2 - x_shift + 1][y2 - y_shift + 1][z2 - z_shift + 1][logx][logy][logz] }; Cell best = cells[0]; for (auto& c : cells) if (c.value > best.value) best = c; return {best.value, best.pos}; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, k; std::cin >> n >> m >> k; int a, b, c; std::cin >> a >> b >> c; Tensor field(n, Matrix(m, std::vector
(k))); SparseTable table(n, SparseTable2d(m, std::vector
(k, field))); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { for (int o = 0; o < k; ++o) { int val; std::cin >> val; field[i][j][o] = {val, {i, j, o}}; table[i][j][o][0][0][0] = {val, {i, j, o}}; } } } int log_n = std::log2(n); int log_m = std::log2(m); int log_k = std::log2(k); for (int px = 1; px <= log_n; ++px) for (int i = 0; i + (1 << px) - 1 < n; ++i) for (int j = 0; j < m; ++j) for (int o = 0; o < k; ++o) table[i][j][o][px][0][0] = maxCell(table[i][j][o][px - 1][0][0], table[i + (1 << (px - 1))][j][o][px - 1][0][0]); for (int py = 1; py <= log_m; ++py) for (int i = 0; i < n; ++i) for (int j = 0; j + (1 << py) - 1 < m; ++j) for (int o = 0; o < k; ++o) table[i][j][o][0][py][0] = maxCell(table[i][j][o][0][py - 1][0], table[i][j + (1 << (py - 1))][o][0][py - 1][0]); for (int pz = 1; pz <= log_k; ++pz) for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) for (int o = 0; o + (1 << pz) - 1 < k; ++o) table[i][j][o][0][0][pz] = maxCell(table[i][j][o][0][0][pz - 1], table[i][j][o + (1 << (pz - 1))][0][0][pz - 1]); for (int px = 1; px <= log_n; ++px) for (int py = 1; py <= log_m; ++py) for (int i = 0; i + (1 << px) - 1 < n; ++i) for (int j = 0; j + (1 << py) - 1 < m; ++j) for (int o = 0; o < k; ++o) { Cell v1 = table[i][j][o][px - 1][py - 1][0]; Cell v2 = table[i + (1 << (px - 1))][j][o][px - 1][py - 1][0]; Cell v3 = table[i][j + (1 << (py - 1))][o][px - 1][py - 1][0]; Cell v4 = table[i + (1 << (px - 1))][j + (1 << (py - 1))][o][px - 1][py - 1][0]; table[i][j][o][px][py][0] = maxCell(maxCell(v1, v2), maxCell(v3, v4)); } for (int px = 1; px <= log_n; ++px) for (int pz = 1; pz <= log_k; ++pz) for (int i = 0; i + (1 << px) - 1 < n; ++i) for (int j = 0; j < m; ++j) for (int o = 0; o + (1 << pz) - 1 < k; ++o) { Cell v1 = table[i][j][o][px - 1][0][pz - 1]; Cell v2 = table[i + (1 << (px - 1))][j][o][px - 1][0][pz - 1]; Cell v3 = table[i][j][o + (1 << (pz - 1))][px - 1][0][pz - 1]; Cell v4 = table[i + (1 << (px - 1))][j][o + (1 << (pz - 1))][px - 1][0][pz - 1]; table[i][j][o][px][0][pz] = maxCell(maxCell(v1, v2), maxCell(v3, v4)); } for (int py = 1; py <= log_m; ++py) for (int pz = 1; pz <= log_k; ++pz) for (int i = 0; i < n; ++i) for (int j = 0; j + (1 << py) - 1 < m; ++j) for (int o = 0; o + (1 << pz) - 1 < k; ++o) { Cell v1 = table[i][j][o][0][py - 1][pz - 1]; Cell v2 = table[i][j + (1 << (py - 1))][o][0][py - 1][pz - 1]; Cell v3 = table[i][j][o + (1 << (pz - 1))][0][py - 1][pz - 1]; Cell v4 = table[i][j + (1 << (py - 1))][o + (1 << (pz - 1))][0][py - 1][pz - 1]; table[i][j][o][0][py][pz] = maxCell(maxCell(v1, v2), maxCell(v3, v4)); } for (int px = 1; px <= log_n; ++px) for (int py = 1; py <= log_m; ++py) for (int pz = 1; pz <= log_k; ++pz) for (int i = 0; i + (1 << px) - 1 < n; ++i) for (int j = 0; j + (1 << py) - 1 < m; ++j) for (int o = 0; o + (1 << pz) - 1 < k; ++o) { int x1 = i, y1 = j, z1 = o; int x2 = i + (1 << (px - 1)); int y2 = j + (1 << (py - 1)); int z2 = o + (1 << (pz - 1)); Cell v1 = table[x1][y1][z1][px - 1][py - 1][pz - 1]; Cell v2 = table[x2][y1][z1][px - 1][py - 1][pz - 1]; Cell v3 = table[x1][y2][z1][px - 1][py - 1][pz - 1]; Cell v4 = table[x2][y2][z1][px - 1][py - 1][pz - 1]; Cell v5 = table[x1][y1][z2][px - 1][py - 1][pz - 1]; Cell v6 = table[x2][y1][z2][px - 1][py - 1][pz - 1]; Cell v7 = table[x1][y2][z2][px - 1][py - 1][pz - 1]; Cell v8 = table[x2][y2][z2][px - 1][py - 1][pz - 1]; table[i][j][o][px][py][pz] = maxCell(maxCell(maxCell(v1, v2), maxCell(v3, v4)), maxCell(maxCell(v5, v6), maxCell(v7, v8))); } int q; std::cin >> q; Vector3 size = {a, b, c}; while (q-- > 0) { int x; int y; int z; std::cin >> x >> y >> z; Vector3 start = {x, y, z}; QueryResult res = query_max(table, start, size); while (res.pos != start) { start = res.pos; res = query_max(table, start, size); } std::cout << res.pos.x << " " << res.pos.y << " " << res.pos.z << "\n"; } } /* 39 94 94 63 27 79 10 69 28 86 61 79 97 78 64 23 94 94 94 86 86 79 97 86 79 */
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)