結果

問題 No.2786 RMQ on Grid Path
ユーザー Bảo Vương
提出日時 2025-08-05 15:43:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,307 bytes
コンパイル時間 2,891 ms
コンパイル使用メモリ 240,716 KB
実行使用メモリ 12,552 KB
最終ジャッジ日時 2025-08-05 15:44:12
合計ジャッジ時間 13,369 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other WA * 6 RE * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int MAXN = 500;
const int MAXQ = 400000;
const int DIR[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

int n, q;
int a[MAXN][MAXN];
vector<tuple<int, int, int, int>> queries_info;

vector<int> parent, comp_size;
vector<bool> activated;
vector<set<pair<int, pair<int, int>>>> query_set;
vector<int> ans;
vector<vector<vector<pair<int, pair<int, int>>>>> cell_queries;

int find(int u) {
    if (parent[u] != u) {
        parent[u] = find(parent[u]);
    }
    return parent[u];
}

void merge(int comp1, int comp2, int value) {
    auto it = query_set[comp1].begin();
    while (it != query_set[comp1].end()) {
        int qid = it->first;
        pair<int, int> other_end = it->second;
        int idx_other = other_end.first * n + other_end.second;
        int comp_other = find(idx_other);
        if (comp_other == comp2) {
            ans[qid] = value;
            it = query_set[comp1].erase(it);
        } else {
            it++;
        }
    }

    it = query_set[comp2].begin();
    while (it != query_set[comp2].end()) {
        int qid = it->first;
        pair<int, int> other_end = it->second;
        int idx_other = other_end.first * n + other_end.second;
        int comp_other = find(idx_other);
        if (comp_other == comp1) {
            ans[qid] = value;
            it = query_set[comp2].erase(it);
        } else {
            it++;
        }
    }

    if (query_set[comp1].size() < query_set[comp2].size()) {
        swap(query_set[comp1], query_set[comp2]);
    }
    for (const auto& elem : query_set[comp2]) {
        query_set[comp1].insert(elem);
    }
    set<pair<int, pair<int, int>>>().swap(query_set[comp2]);

    parent[comp2] = comp1;
    comp_size[comp1] += comp_size[comp2];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    cell_queries.resize(n, vector<vector<pair<int, pair<int, int>>>>(n));
    queries_info.resize(q);
    for (int i = 0; i < q; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1--; y1--; x2--; y2--;
        queries_info[i] = {x1, y1, x2, y2};
        cell_queries[x1][y1].push_back({i, {x2, y2}});
        cell_queries[x2][y2].push_back({i, {x1, y1}});
    }

    vector<tuple<int, int, int>> cells;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cells.push_back(make_tuple(a[i][j], i, j));
        }
    }
    sort(cells.rbegin(), cells.rend());

    int total = n * n;
    parent.resize(total);
    comp_size.resize(total, 0);
    activated.resize(total, false);
    query_set.resize(total);
    ans.resize(q, -1);

    for (auto &cell : cells) {
        int value = get<0>(cell);
        int i = get<1>(cell);
        int j = get<2>(cell);
        int idx = i * n + j;

        activated[idx] = true;
        parent[idx] = idx;
        comp_size[idx] = 1;
        query_set[idx].clear();

        for (auto &qry : cell_queries[i][j]) {
            int qid = qry.first;
            pair<int, int> other_end = qry.second;
            int x2 = other_end.first, y2 = other_end.second;
            int idx_other = x2 * n + y2;

            if (activated[idx_other]) {
                int comp_other = find(idx_other);
                int comp_this = find(idx);
                if (comp_this == comp_other) {
                    continue;
                }
                query_set[comp_this].insert({qid, {x2, y2}});
            }
        }

        for (int d = 0; d < 4; d++) {
            int ni = i + DIR[d][0];
            int nj = j + DIR[d][1];
            if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
            int nidx = ni * n + nj;
            if (!activated[nidx]) continue;

            int comp1 = find(idx);
            int comp2 = find(nidx);
            if (comp1 == comp2) continue;

            if (comp_size[comp1] < comp_size[comp2]) {
                swap(comp1, comp2);
            }
            merge(comp1, comp2, value);
        }
    }

    int min_val = get<0>(cells.back());
    for (int i = 0; i < q; i++) {
        if (ans[i] == -1) {
            ans[i] = min_val;
        }
        cout << ans[i] << '\n';
    }

    return 0;
}
0