結果

問題 No.2786 RMQ on Grid Path
ユーザー 👑 seekworser
提出日時 2024-06-13 21:49:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 928 ms / 6,000 ms
コード長 3,049 bytes
コンパイル時間 7,052 ms
コンパイル使用メモリ 308,024 KB
実行使用メモリ 87,236 KB
最終ジャッジ日時 2024-06-14 20:54:11
合計ジャッジ時間 27,105 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include "atcoder/dsu.hpp"
#include "atcoder/segtree.hpp"
using namespace std;
const int INF = 1 << 30;
const vector<pair<int,int>> dxy = {{0,1},{0,-1},{1,0},{-1,0}};

int op_min(int a, int b) { return min(a, b); }
int e_min() { return INF; }
int op_max(int a, int b) { return max(a, b); }
int e_max() { return -INF; }
vector<int> order;
vector<int> depth;
vector<int> visited;
void eulertour(const vector<vector<int>> &g) {
    int n = g.size();
    visited = vector<int>(n, 2*n);
    auto dfs = [&](auto self, int u, int d, int parent) -> void {
        if (visited[u] == 2*n) visited[u] = order.size();
        order.push_back(u);
        depth.push_back(d);
        for (int v : g[u]) {
            if (v != parent) self(self, v, d+1, u);
            order.push_back(u);
            depth.push_back(d);
        }
    };
    dfs(dfs, 0, 0, -1);
    return;
}

int main() {
    int h,w; cin >> h >> w;
    vector a(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }
    vector<tuple<int,int,int>> edges;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            for (auto [dx, dy] : dxy) {
                if (i+dx < 0 || i+dx >= h || j+dy < 0 || j+dy >= w) continue;
                edges.emplace_back(max(a[i][j], a[i+dx][j+dy]), i*w+j, (i+dx)*w+(j+dy));
            }
        }
    }
    sort(edges.begin(), edges.end());
    vector<vector<int>> g = [&]() {
        atcoder::dsu uf(h*w);
        vector<vector<int>> g(h*w);
        for (auto [cost, u, v] : edges) {
            if (!uf.same(u, v)) {
                uf.merge(u, v);
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
        return g;
    }();
    eulertour(g);
    atcoder::segtree<int, op_min, e_min> seg_depth(depth);
    auto lca = [&](int u, int v) -> int {
        if (visited[u] > visited[v]) swap(u, v);
        int min_depth = seg_depth.prod(visited[u], visited[v]+1);
        int lca_pos = seg_depth.max_right(visited[u], [&](int x) -> bool { return x > min_depth;});
        return order[lca_pos];
    };
    int q; cin >> q;
    vector<vector<tuple<int,int>>> query(2*h*w);
    for (int i = 0; i < q; i++) {
        int rs, cs, rt, ct; cin >> rs >> cs >> rt >> ct;
        int u = (rs-1)*w+(cs-1);
        int v = (rt-1)*w+(ct-1);
        int l = lca(u, v);
        query[u].push_back({depth[visited[l]], i});
        query[v].push_back({depth[visited[l]], i});
    }
    atcoder::segtree<int, op_max, e_max> seg_query(h*w);
    vector<int> ans (q, -INF);
    auto dfs = [&] (auto self, int u, int parent) -> void {
        int val = a[u/w][u%w];
        seg_query.set(depth[visited[u]], val);
        for (auto [d, id] : query[u]) {
            ans[id] = max(ans[id], seg_query.prod(d, h*w));
        }
        for (auto v : g[u]) if (v != parent) self(self, v, u);
        seg_query.set(depth[visited[u]], -INF);
    };
    dfs(dfs, 0, -1);
    for (auto x : ans) cout << x << '\n';
}
0