結果
問題 | No.2786 RMQ on Grid Path |
ユーザー |
![]() |
提出日時 | 2024-06-14 22:47:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,271 ms / 6,000 ms |
コード長 | 3,107 bytes |
コンパイル時間 | 2,945 ms |
コンパイル使用メモリ | 230,136 KB |
最終ジャッジ日時 | 2025-02-21 22:16:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } class UnionFind { public: vector<map<int, int>> par_or_rank; void init(int n) { par_or_rank.resize(n); for (int i = 0; i < n; i++) { par_or_rank[i][0] = -1; } }; int leader(int u, int t = 1e9) { auto it = par_or_rank[u].lower_bound(t + 1); it--; int p = it->second; if (p < 0) { return u; } return leader(p, t); } bool same(int u, int v, int t = 1e9) { return leader(u, t) == leader(v, t); } void merge(int u, int v, int t) { u = leader(u, 1e9); v = leader(v, 1e9); if (u == v) { return; } if (-par_or_rank[u].rbegin()->second < -par_or_rank[v].rbegin()->second) { swap(u, v); } par_or_rank[u][t] = par_or_rank[u].rbegin()->second + par_or_rank[v].rbegin()->second; par_or_rank[v][t] = u; } }; int main() { fast_io(); 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]; } } vector<tuple<int, int, int>> edges; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { int id = i * w + j; if (i + 1 < h) { int id2 = (i + 1) * w + j; int cost = max(a[i][j], a[i + 1][j]); edges.emplace_back(cost, id, id2); } if (j + 1 < w) { int id2 = i * w + j + 1; int cost = max(a[i][j], a[i][j + 1]); edges.emplace_back(cost, id, id2); } } } sort(edges.begin(), edges.end()); UnionFind uf; uf.init(h * w); for (auto [cost, u, v] : edges) { uf.merge(u, v, cost); } int q; cin >> q; vector<int> rs(q), cs(q), rt(q), ct(q); for (int i = 0; i < q; i++) { cin >> rs[i] >> cs[i] >> rt[i] >> ct[i]; rs[i]--; cs[i]--; rt[i]--; ct[i]--; } vector<int> ans(q); map<pair<int, int>, vector<int>> mp; for (int i = 0; i < q; i++) { mp[{0, h * w}].push_back(i); } while (!mp.empty()) { auto [l, r] = mp.begin()->first; auto qs = mp.begin()->second; mp.erase(mp.begin()); if (l + 1 == r) { for (int i : qs) { ans[i] = r; } continue; } int mid = (l + r) / 2; vector<int> lq, rq; for (int i : qs) { if (uf.same(rs[i] * w + cs[i], rt[i] * w + ct[i], mid)) { lq.push_back(i); } else { rq.push_back(i); } } if (!lq.empty()) { mp[{l, mid}] = lq; } if (!rq.empty()) { mp[{mid, r}] = rq; } } for (int i = 0; i < q; i++) { cout << ans[i] << "\n"; } }