結果

問題 No.2786 RMQ on Grid Path
ユーザー 👑 seekworserseekworser
提出日時 2024-06-13 21:37:58
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,042 bytes
コンパイル時間 4,535 ms
コンパイル使用メモリ 279,060 KB
実行使用メモリ 80,432 KB
最終ジャッジ日時 2024-06-14 20:54:05
合計ジャッジ時間 21,943 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 3 ms
6,940 KB
testcase_09 WA -
testcase_10 AC 2 ms
6,944 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 546 ms
58,676 KB
testcase_23 AC 553 ms
59,028 KB
testcase_24 AC 626 ms
80,200 KB
testcase_25 AC 632 ms
80,176 KB
testcase_26 AC 665 ms
80,148 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 620 ms
61,020 KB
testcase_33 AC 133 ms
7,396 KB
testcase_34 AC 607 ms
80,380 KB
testcase_35 AC 605 ms
80,288 KB
testcase_36 AC 614 ms
80,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include "atcoder/dsu.hpp"
#include "atcoder/segtree.hpp"
using namespace std;
// using ll = long long;
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