結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー pitP
提出日時 2024-06-17 22:59:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,250 ms / 6,000 ms
コード長 6,992 bytes
コンパイル時間 7,759 ms
コンパイル使用メモリ 337,732 KB
実行使用メモリ 57,672 KB
最終ジャッジ日時 2024-06-17 22:59:58
合計ジャッジ時間 38,332 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }
istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }
istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } 

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)
#define rep(i,n) for (int i = 0;i < (int)(n); i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define my_sort(x) sort(x.begin(), x.end())
#define my_max(x) *max_element(all(x))
#define my_min(x) *min_element(all(x))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<62) - 1;
const int MOD = 998244353;
const int MOD2 = 1e9+7;
const double PI = acos(-1);
vector<int> di = {1,0,-1,0};
vector<int> dj = {0,1,0,-1};

#ifdef LOCAL
#  include <debug_print.hpp>
#  define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#  define debug(...) (static_cast<void>(0))
#endif

// HL-Decomposition
// vid: id of v after HL-Decomposition
// inv: inv[vid[v]] = v
// par: id of parent
// depth
// subsize: size of subtree
// head: head-id in the heavy-path
// prev, next: prev-id, next-id in the heavy-path
// type: the id of tree for forest
// vend: the last-id of node in v-subtree
typedef vector<vector<int> > Graph;
struct HLDecomposition {
    int n;
    Graph G;
    vector<int> vid, inv, par, depth, subsize, head, prev, next, type;
    
    // construct
    HLDecomposition() { }
    HLDecomposition(const Graph &G_) :
        n((int)G_.size()), G(G_),
        vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1),
        head(n), prev(n, -1), next(n, -1), type(n) { }
    void build(vector<int> roots = {0}) {
        int curtype = 0, pos = 0;
        for (auto r : roots) decide_heavy_edge(r), reconstruct(r, curtype++, pos);
    }
    void decide_heavy_edge(int r) {
        stack<pair<int,int> > st;
        par[r] = -1, depth[r] = 0;
        st.emplace(r, 0);
        while (!st.empty()) {
            int v = st.top().first;
            int &i = st.top().second;
            if (i < (int)G[v].size()) {
                int e = G[v][i++];
                if (e == par[v]) continue;
                par[e] = v, depth[e] = depth[v] + 1;
                st.emplace(e, 0);
            }
            else {
                st.pop();
                int maxsize = 0;
                for (auto e : G[v]) {
                    if (e == par[v]) continue;
                    subsize[v] += subsize[e];
                    if (maxsize < subsize[e]) maxsize = subsize[e], prev[e] = v, next[v] = e;
                }
            }
        }
    }
    void reconstruct(int r, int curtype, int &pos) {
        stack<int> st({r});
        while (!st.empty()) {
            int start = st.top(); st.pop();
            for (int v = start; v != -1; v = next[v]) {
                type[v] = curtype;
                vid[v] = pos++;
                inv[vid[v]] = v;
                head[v] = start;
                for (auto e : G[v]) if (e != par[v] && e != next[v]) st.push(e);
            }
        }
    }
    
    // node query [u, v], f([left, right])
    void foreach_nodes(int u, int v, const function<void(int,int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            f(max(vid[head[v]], vid[u]), vid[v]);
            if (head[u] != head[v]) v = par[head[v]];
            else break;
        }
    }
    
    // edge query [u, v], f([left, right])
    void foreach_edges(int u, int v, const function<void(int,int)> &f) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] != head[v]) {
                f(vid[head[v]], vid[v]);
                v = par[head[v]];
            }
            else {
                if (u != v) {
                    f(vid[u]+1, vid[v]);
                }
                break;
            }
        }
    }

    // https://atcoder.jp/contests/abc138/submissions/38833623
    void subtree_nodes(int v, const function<void(int,int)> &f) {
        f(vid[v],vid[v]+subsize[v]);
    }

    // https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7464630#1
    void subtree_edges(int v, const function<void(int,int)> &f) {
        f(vid[v] + 1, vid[v] + subsize[v]);
    }

    // LCA
    int lca(int u, int v) {
        while (true) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }
};
// https://drken1215.hatenablog.com/entry/2018/08/14/193500
// hld.build()忘れない !!!
//
// [path_query]
// hld.foreach_nodes(v,[&](int l, int r) {seg.apply(l,r+1,x);});
// hld.foreach_edges(v,[&](int l, int r) {seg.apply(l,r+1,x);});
//
// [subtree_query]
// hld.subtree_nodes(v,[&](int l, int r) {seg.apply(l,r,x);});
// hld.subtree_edges(v,[&](int l, int r) {seg.apply(l,r,x);});

using S = int;
using F = int;
S op(S a, S b){return max(a, b);}
S e(){return 0;}
S mapping(F f, S x){return f + x;}
F composition(F f, F g){return f + g;}
F id(){return 0;}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int H, W; cin >> H >> W;
    vector A(H, vector<int>(W));
    rep(i, H)rep(j, W) cin >> A[i][j];

    // Kruskal
    using P = tuple<int,int,int>;
    vector<P> edges;
    rep(i, H)rep(j, W){
        rep(d, 4){
            int ni = i + di[d], nj = j + dj[d];
            if(ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
            edges.push_back(P{max(A[i][j], A[ni][nj]), i * W + j, ni * W + nj});
        }
    }
    sort(all(edges));
    debug(edges);

    int V = H * W;
    Graph g(V);
    dsu uf(V);
    for(auto &[_, u, v]: edges)if(!uf.same(u, v)){
        uf.merge(u, v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    HLDecomposition hld(g);
    hld.build();

    vector<S> dat(V, 0);
    lazy_segtree<S,op,e,F,mapping,composition,id> seg(dat);
    rep(v, V)for(auto &u : g[v])if(v < u){
        int cost = max(A[v/W][v%W], A[u/W][u%W]);
        hld.foreach_edges(v, u, [&](int l, int r) {seg.apply(l, r + 1, cost);});
    }

    int Q; cin >> Q;
    while(Q--){
        int si, sj;
        int gi, gj;
        cin >> si >> sj;
        cin >> gi >> gj;
        si--;
        sj--;
        gi--;
        gj--;

        int ans = 0;
        hld.foreach_edges(si * W + sj, gi * W + gj, [&](int l, int r){chmax(ans, seg.prod(l, r + 1)); });
        cout << ans << endl;
    }
}
0