結果
問題 | No.2786 RMQ on Grid Path |
ユーザー |
![]() |
提出日時 | 2024-06-14 23:16:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,565 ms / 6,000 ms |
コード長 | 4,437 bytes |
コンパイル時間 | 1,512 ms |
コンパイル使用メモリ | 115,080 KB |
最終ジャッジ日時 | 2025-02-21 22:25:45 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
#include <iostream> #include <vector> #include <set> #include <cmath> #include <cassert> using namespace std; class DSU { public: int n; vector<int> parent_or_size; DSU(int N) { n = N; parent_or_size.resize(N, -1); } int leader(int a) { assert(0 <= a && a < n); if (parent_or_size[a] < 0) { return a; } return parent_or_size[a] = leader(parent_or_size[a]); } int merge(int a, int b) { assert(0 <= a && a < n); assert(0 <= b && b < n); int x = leader(a); int y = leader(b); if (x == y) { return x; } if (-parent_or_size[x] < -parent_or_size[y]) { swap(x, y); } parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < n); assert(0 <= b && b < n); return leader(a) == leader(b); } int size(int a) { assert(0 <= a && a < n); return -parent_or_size[leader(a)]; } vector<vector<int>> groups() { vector<int> leader_buf(n); vector<int> group_size(n, 0); for (int i = 0; i < n; ++i) { leader_buf[i] = leader(i); ++group_size[leader_buf[i]]; } vector<vector<int>> result(n); for (int i = 0; i < n; ++i) { result[leader_buf[i]].push_back(i); } vector<vector<int>> result2; for (int i = 0; i < n; ++i) { if (!result[i].empty()) { result2.push_back(result[i]); } } return result2; } }; int main() { int H, W; cin >> H >> W; vector<vector<int>> A(H, vector<int>(W)); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { cin >> A[i][j]; } } set<int> C; vector<pair<int, int>> q; int Q; cin >> Q; for (int i = 0; i < Q; ++i) { int a, b, c, d; cin >> a >> b >> c >> d; q.push_back({(a - 1) * W + (b - 1), (c - 1) * W + (d - 1)}); C.insert(i); } vector<vector<pair<int, int>>> L(H * W + 1); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (i < H - 1) { int x = A[i][j]; int y = A[i + 1][j]; int z = max(x, y); L[z].push_back({i * W + j, (i + 1) * W + j}); } if (j < W - 1) { int x = A[i][j]; int y = A[i][j + 1]; int z = max(x, y); L[z].push_back({i * W + j, i * W + j + 1}); } } } vector<int> result(Q, 0); DSU Z(H * W); int k = static_cast<int>(sqrt(H * W)); int M = (H * W + k - 1) / k; vector<vector<int>> D(M + 1); vector<bool> ans(Q, false); for (int i = 0; i <= M; ++i) { int l = i * k; int r = (i + 1) * k; for (int j = 0; j < k; ++j) { int z = i * k + j; if (z > H * W) { break; } for (auto& B : L[z]) { int pos1 = B.first, pos2 = B.second; Z.merge(pos1, pos2); } } for (int j = 0; j < Q; ++j) { int p1 = q[j].first, p2 = q[j].second; if (ans[j]) { continue; } if (Z.same(p1, p2)) { ans[j] = true; D[i].push_back(j); } } } Z = DSU(H * W); fill(ans.begin(), ans.end(), false); for (int i = 0; i <= M; ++i) { for (int j = 0; j < k; ++j) { int z = i * k + j; if (z > H * W) { break; } for (auto& B : L[z]) { int pos1 = B.first, pos2 = B.second; Z.merge(pos1, pos2); } if (!L[z].empty()) { for (int idx : D[i]) { int p1 = q[idx].first, p2 = q[idx].second; if (ans[idx]) { continue; } if (Z.same(p1, p2)) { ans[idx] = true; result[idx] = z; } } } } } for (int i = 0; i < Q; ++i) { cout << result[i] << endl; } return 0; }