結果
問題 | No.2786 RMQ on Grid Path |
ユーザー |
|
提出日時 | 2024-06-14 22:28:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,288 ms / 6,000 ms |
コード長 | 2,258 bytes |
コンパイル時間 | 2,648 ms |
コンパイル使用メモリ | 216,872 KB |
最終ジャッジ日時 | 2025-02-21 22:11:36 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; class UnionFind{ public: vector<int> par,siz; vector<set<int>> Query; void make(int N,vector<pair<int,int>> Q){ par.resize(N,-1); siz.resize(N,1); Query.resize(N); for(int i=0; i<Q.size(); i++){ auto[a,b] = Q.at(i); Query.at(a).insert(i); Query.at(b).insert(i); } } int root(int x){ if(par.at(x) == -1) return x; else return par.at(x) = root(par.at(x)); } vector<int> unite(int u, int v){ u = root(u),v = root(v); if(u == v) return {}; if(Query.at(u).size() < Query.at(v).size()) swap(u,v); par.at(v) = u; siz.at(u) += siz.at(v); vector<int> ret; for(auto &pos : Query.at(v)){ if(Query.at(u).count(pos)){ret.push_back(pos),Query.at(u).erase(pos);} else Query.at(u).insert(pos); } Query.at(v).clear(); return ret; } bool issame(int u, int v){ if(root(u) == root(v)) return true; else return false; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int H,W; cin >> H >> W; vector<vector<int>> rev(1000000); vector<vector<int>> A(H,vector<int>(W)); for(int i=0; i<H; i++) for(int k=0; k<W; k++){ int a; cin >> a; A.at(i).at(k) = a; rev.at(a).push_back(i*W+k); } int Q; cin >> Q; vector<int> answer(Q); vector<pair<int,int>> Query; while(Q--){ int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--; x2--; y2--; Query.push_back({x1*W+y1,x2*W+y2}); } Q = answer.size(); UnionFind Z; Z.make(H*W,Query); vector<pair<int,int>> dxy = {{-1,0},{0,1},{1,0},{0,-1}}; for(int i=0; i<1000000; i++) for(auto r : rev.at(i)){ int x = r/W,y = r%W; for(auto [dx,dy] : dxy){ int nx = x+dx,ny = y+dy; if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue; if(A.at(nx).at(ny) <= A.at(x).at(y)){ auto now = Z.unite(x*W+y,nx*W+ny); for(auto pos : now) answer.at(pos) = i; } } } for(auto ans : answer) cout << ans << "\n"; }