結果
問題 |
No.2786 RMQ on Grid Path
|
ユーザー |
|
提出日時 | 2024-06-17 03:10:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,210 ms / 6,000 ms |
コード長 | 1,555 bytes |
コンパイル時間 | 3,719 ms |
コンパイル使用メモリ | 268,100 KB |
実行使用メモリ | 70,952 KB |
最終ジャッジ日時 | 2024-06-17 03:10:52 |
合計ジャッジ時間 | 29,185 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/dsu> using namespace std; using namespace atcoder; using ll = long long; constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll H, W; cin >> H >> W; vector<vector<ll>> A(H, vector<ll>(W)); vector<vector<pair<ll, ll>>> v(H * W); for(ll i = 0; i < H; i++) { for(ll j = 0; j < W; j++) { cin >> A[i][j]; v[--A[i][j]].emplace_back(i, j); } } ll Q; cin >> Q; vector<tuple<ll, ll, ll, ll>> q(Q); for(auto &[sx, sy, tx, ty] : q) { cin >> sx >> sy >> tx >> ty; sx--, sy--, tx--, ty--; } vector<ll> L(Q, 0), R(Q, H * W); vector<vector<ll>> ask(H * W); while(true) { bool fin = true; for(ll i = 0; i < Q; i++) { if(R[i] - L[i] > 1) { fin = false; ask[(L[i] + R[i]) / 2].emplace_back(i); } } if(fin) { break; } dsu u(H * W); auto idx = [&](ll i, ll j) { return i * W + j; }; for(ll M = 0; M < H * W; M++) { while(!ask[M].empty()) { ll i = ask[M].back(); ask[M].pop_back(); auto [sx, sy, tx, ty] = q[i]; u.same(idx(sx, sy), idx(tx, ty)) ? R[i] = M : L[i] = M; } for(auto &[i, j] : v[M]) { for(ll k = 0; k < 4; k++) { ll ni = i + dx[k], nj = j + dy[k]; if(ni < 0 || ni >= H || nj < 0 || nj >= W) { continue; } if(A[ni][nj] <= A[i][j]) { u.merge(idx(i, j), idx(ni, nj)); } } } } } for(auto &i : L) { cout << ++i << "\n"; } }