結果

問題 No.2786 RMQ on Grid Path
ユーザー 👑 seekworserseekworser
提出日時 2024-06-13 21:49:54
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 3 ms
6,816 KB
testcase_03 AC 3 ms
6,816 KB
testcase_04 AC 3 ms
6,816 KB
testcase_05 AC 3 ms
6,944 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 915 ms
67,920 KB
testcase_13 AC 908 ms
68,380 KB
testcase_14 AC 907 ms
69,312 KB
testcase_15 AC 915 ms
68,532 KB
testcase_16 AC 928 ms
67,384 KB
testcase_17 AC 904 ms
67,556 KB
testcase_18 AC 903 ms
67,516 KB
testcase_19 AC 917 ms
68,148 KB
testcase_20 AC 911 ms
68,196 KB
testcase_21 AC 910 ms
67,276 KB
testcase_22 AC 683 ms
65,528 KB
testcase_23 AC 684 ms
66,752 KB
testcase_24 AC 761 ms
86,336 KB
testcase_25 AC 760 ms
86,284 KB
testcase_26 AC 779 ms
86,692 KB
testcase_27 AC 311 ms
19,080 KB
testcase_28 AC 266 ms
10,496 KB
testcase_29 AC 730 ms
63,568 KB
testcase_30 AC 263 ms
12,436 KB
testcase_31 AC 40 ms
6,944 KB
testcase_32 AC 773 ms
67,332 KB
testcase_33 AC 148 ms
7,392 KB
testcase_34 AC 749 ms
86,524 KB
testcase_35 AC 751 ms
87,236 KB
testcase_36 AC 750 ms
87,224 KB
権限があれば一括ダウンロードができます

ソースコード

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