結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー V_Melville
提出日時 2025-02-23 16:31:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 797 ms / 6,000 ms
コード長 1,784 bytes
コンパイル時間 5,992 ms
コンパイル使用メモリ 333,780 KB
実行使用メモリ 20,908 KB
最終ジャッジ日時 2025-02-23 16:31:41
合計ジャッジ時間 30,180 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int main() {
    int h, w;
    cin >> h >> w;
    
    vector<tuple<int, int, int>> buildings;
    rep(i, h)rep(j, w) {
        int f;
        cin >> f;
        buildings.emplace_back(f, i, j);
    }
    int n = h*w;
    
    ranges::sort(buildings);
    
    int q;
    cin >> q;
    vector<tuple<int, int, int, int>> qs;
    rep(qi, q) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a; --b; --c; --d;
        qs.emplace_back(a, b, c, d);
    }
    
    vector<int> ac(q, n-1), wa(q, -1);
    rep(ti, 20) {
        vector<vector<int>> qis(n);
        rep(qi, q) {
            if (wa[qi]+1 < ac[qi]) {
                int wj = (ac[qi]+wa[qi])/2;
                qis[wj].push_back(qi);
            }
        }
        
        dsu uf(n);
        vector<bool> canPass(n);
        rep(bi, n) {
            auto [f, i, j] = buildings[bi];
            int v = i*w+j;
            canPass[v] = true;
            rep(dir, 4) {
                int ni = i+di[dir], nj = j+dj[dir];
                if (ni < 0 or nj < 0 or ni >= h or nj >= w) continue;
                int u = ni*w+nj;
                if (!canPass[u]) continue;
                uf.merge(v, u);
            }
            
            for (int qi : qis[bi]) {
                auto [a, b, c, d] = qs[qi];
                int s = a*w+b, t = c*w+d;
                if (uf.same(s, t)) ac[qi] = bi; else wa[qi] = bi;
            }
        }
    }
    
    rep(qi, q) {
        auto [a, b, c, d] = qs[qi];
        int ans = get<0>(buildings[ac[qi]]);
        cout << ans << '\n';
    }
    
    return 0;
}
0