#1000122 (C++23) No.2786 RMQ on Grid Path

• 問題: No.2786 RMQ on Grid Path
• ユーザー: detteiuu
• 提出日時: 2024-08-07 02:49:07
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 725 ms / 6,000 ms
• コード長: 3,449 bytes
• コンパイル時間: 1,549 ms
• コンパイル使用メモリ: 188,676 KB
• 実行使用メモリ: 59,532 KB
• 最終ジャッジ日時: 2026-04-03 20:10:03
• 合計ジャッジ時間: 21,840 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 35

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class UnionFind {
public:
    vector<int> parent_size;
    UnionFind(int n) : parent_size(n, -1) {}

    int leader(int a) {
        if (parent_size[a] < 0) {
            return a;
        }
        return parent_size[a] = leader(parent_size[a]);
    }

    void merge(int a, int b) {
        int x = leader(a);
        int y = leader(b);
        if (x == y) return;
        if (abs(parent_size[x]) < abs(parent_size[y])) {
            swap(x, y);
        }
        parent_size[x] += parent_size[y];
        parent_size[y] = x;
    }

    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    int size(int a) {
        return abs(parent_size[leader(a)]);
    }

    vector<vector<int>> groups(int n) {
        vector<vector<int>> result(n);
        for (int i = 0; i < n; ++i) {
            result[leader(i)].push_back(i);
        }
        vector<vector<int>> filtered_result;
        for (const auto& r : result) {
            if (!r.empty()) {
                filtered_result.push_back(r);
            }
        }
        return filtered_result;
    }
};

int IDX(int i, int j, int W) {
    return i * W + j;
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> A(H, vector<int>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
        }
    }

    int Q;
    cin >> Q;
    vector<vector<int>> query(Q, vector<int>(4));
    for (int i = 0; i < Q; ++i) {
        cin >> query[i][0] >> query[i][1] >> query[i][2] >> query[i][3];
    }

    vector<tuple<int, int, int>> edge;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (i + 1 < H) {
                edge.emplace_back(IDX(i, j, W), IDX(i + 1, j, W), max(A[i][j], A[i + 1][j]));
            }
            if (j + 1 < W) {
                edge.emplace_back(IDX(i, j, W), IDX(i, j + 1, W), max(A[i][j], A[i][j + 1]));
            }
        }
    }

    sort(edge.begin(), edge.end(), [](const auto& a, const auto& b) {
        return get<2>(a) < get<2>(b);
    });

    vector<int> left(Q, 0), right(Q, edge.size());
    vector<vector<int>> mid(edge.size() + 1);
    for (int i = 0; i < Q; ++i) {
        mid[edge.size() / 2].push_back(i);
    }

    int cnt = 0;
    while (cnt < Q) {
        UnionFind UF(H * W);
        for (int i = 0; i <= edge.size(); ++i) {
            if (!mid[i].empty()) {
                while (!mid[i].empty()) {
                    int idx = mid[i].back();
                    mid[i].pop_back();
                    int sh = query[idx][0], sw = query[idx][1];
                    int gh = query[idx][2], gw = query[idx][3];
                    if (UF.same(IDX(sh - 1, sw - 1, W), IDX(gh - 1, gw - 1, W))) {
                        right[idx] = i;
                    } else {
                        left[idx] = i;
                    }
                    if (left[idx] + 1 == right[idx]) {
                        cnt++;
                    } else {
                        mid[(left[idx] + right[idx]) / 2].push_back(idx);
                    }
                }
            }
            if (i < edge.size()) {
                int v, w, c;
                tie(v, w, c) = edge[i];
                UF.merge(v, w);
            }
        }
    }

    for (int i = 0; i < Q; ++i) {
        cout << get<2>(edge[left[i]]) << endl;
    }

    return 0;
}