結果

問題 No.2786 RMQ on Grid Path
ユーザー mkawa2
提出日時 2025-07-03 16:50:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,836 ms / 6,000 ms
コード長 2,737 bytes
コンパイル時間 1,191 ms
コンパイル使用メモリ 98,952 KB
実行使用メモリ 48,032 KB
最終ジャッジ日時 2025-07-03 16:50:42
合計ジャッジ時間 33,268 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <tuple>

class UnionFind {
public:
    UnionFind(int n) : _tree(n, -1), cnt(n) {}

    int root(int u) {
        std::vector<int> stack;
        while (_tree[u] >= 0) {
            stack.push_back(u);
            u = _tree[u];
        }
        for (int v : stack) _tree[v] = u;
        return u;
    }

    bool same(int u, int v) {
        return root(u) == root(v);
    }

    bool merge(int u, int v) {
        u = root(u);
        v = root(v);
        if (u == v) return false;
        if (_tree[u] > _tree[v]) std::swap(u, v);
        _tree[u] += _tree[v];
        _tree[v] = u;
        cnt--;
        return true;
    }

    int size(int u) {
        return -_tree[root(u)];
    }

private:
    std::vector<int> _tree;
    int cnt;
};

int main() {
    int h, w;
    std::cin >> h >> w;
    int n = h * w;
    std::vector<std::vector<int>> aa(h, std::vector<int>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            std::cin >> aa[i][j];
        }
    }

    std::vector<std::vector<std::pair<int, int>>> c2uv(n + 1);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (i) c2uv[std::max(aa[i][j], aa[i - 1][j])].emplace_back(i * w + j, (i - 1) * w + j);
            if (j) c2uv[std::max(aa[i][j], aa[i][j - 1])].emplace_back(i * w + j, i * w + j - 1);
        }
    }

    int q;
    std::cin >> q;
    std::vector<std::pair<int, int>> st;
    for (int _ = 0; _ < q; _++) {
        int i, j, r, c;
        std::cin >> i >> j >> r >> c;
        st.emplace_back((i - 1) * w + (j - 1), (r - 1) * w + (c - 1));
    }

    std::vector<int> l(q, 0);
    std::vector<int> r(q, n);
    std::vector<int> ans(q, -1);
    int cnt = 0;
    std::vector<std::vector<int>> m2i(n + 1);

    while (cnt < q) {
        for (int i = 0; i < q; i++) {
            if (ans[i] == -1) {
                int m = (l[i] + r[i]) / 2;
                m2i[m].push_back(i);
            }
        }
        UnionFind uf(h * w);
        for (int c = 0; c < n; c++) {
            for (const auto& uv : c2uv[c]) {
                uf.merge(uv.first, uv.second);
            }
            while (!m2i[c].empty()) {
                int i = m2i[c].back();
                m2i[c].pop_back();
                int s = st[i].first;
                int t = st[i].second;
                if (uf.same(s, t)) {
                    r[i] = c;
                } else {
                    l[i] = c;
                }
                if (l[i] + 1 == r[i]) {
                    cnt++;
                    ans[i] = r[i];
                }
            }
        }
    }

    for (int i = 0; i < q; i++) {
        std::cout << ans[i] << "\n";
    }

    return 0;
}
0