結果

問題 No.2786 RMQ on Grid Path
ユーザー rgnerdplayer
提出日時 2025-05-01 15:40:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,105 ms / 6,000 ms
コード長 2,905 bytes
コンパイル時間 4,443 ms
コンパイル使用メモリ 292,508 KB
実行使用メモリ 25,568 KB
最終ジャッジ日時 2025-05-01 15:41:31
合計ジャッジ時間 47,144 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

struct DSU {
    int n, cnt;
    vector<int> fa, sz;
    DSU(int n = 0) {
        init(n);
    }
    void init(int n_) {
        n = cnt = n_;
        fa.assign(n, 0);
        iota(fa.begin(), fa.end(), 0);
        sz.assign(n, 1);
    }
    int find(int u) {
        return u == fa[u] ? u : fa[u] = find(fa[u]);
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u != v) {
            // if (sz[u] < sz[v]) { swap(u, v); }
            sz[u] += sz[v];
            fa[v] = u;
            cnt--;
            return true;
        }
        return false;
    }
    bool same(int u, int v) {
        return find(u) == find(v);
    }
    int size(int u) {
        return sz[find(u)];
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    auto solve = [&]() {
        int n, m;
        cin >> n >> m;

        vector a(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> a[i][j];
            }
        }

        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> low(q, 1), high(q, n * m);

        while (true) {
            vector<array<int, 4>> events;
            for (int i = 0; i < q; i++) {
                if (low[i] != high[i]) {
                    events.push_back({(low[i] + high[i]) / 2, 1, i});
                }
            }

            if (events.empty()) {
                break;
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    events.push_back({a[i][j], 0, i, j});
                }
            }

            sort(events.begin(), events.end());

            DSU dsu(n * m);

            for (auto [x, op, i, j] : events) {
                if (op == 0) {
                    for (auto [di, dj] : {pair(1, 0), {0, 1}, {-1, 0}, {0, -1}}) {
                        int ni = i + di, nj = j + dj;
                        if (0 <= ni && ni < n && 0 <= nj && nj < m && a[ni][nj] <= x) {
                            int u = i * m + j;
                            int v = ni * m + nj;
                            dsu.join(u, v);
                        }
                    }
                } else {
                    int u = rs[i] * m + cs[i];
                    int v = rt[i] * m + ct[i];
                    if (dsu.same(u, v)) {
                        high[i] = x;
                    } else {
                        low[i] = x + 1;
                    }
                }
            }
        }

        for (int i = 0; i < q; i++) {
            cout << low[i] << '\n';
        }
    };
    
    solve();
    
    return 0;
}
0