結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー seekworser
提出日時 2024-06-13 21:21:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 9,471 bytes
コンパイル時間 3,648 ms
コンパイル使用メモリ 277,444 KB
実行使用メモリ 31,612 KB
最終ジャッジ日時 2024-06-14 20:53:44
合計ジャッジ時間 12,281 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 10 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

//line 1 "answer.cpp"
#include <bits/stdc++.h>
//line 5 "/home/seekworser/.cpp_lib/competitive_library/atcoder/dsu.hpp"

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
  public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

}  // namespace atcoder
//line 5 "/home/seekworser/.cpp_lib/competitive_library/atcoder/segtree.hpp"

//line 2 "/home/seekworser/.cpp_lib/competitive_library/atcoder/internal_bit.hpp"
#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder
//line 7 "/home/seekworser/.cpp_lib/competitive_library/atcoder/segtree.hpp"

namespace atcoder {

template <class S, S (*_op)(S, S), S (*_e)()> struct segtree {
  public:
    S (*op)(S, S) = _op;
    S (*e)() = _e;
    segtree() : segtree(0) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    explicit segtree(int n) : segtree(std::vector<S>(n, _e())) {}

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    void add(int p, S x) {
        assert(0 <= p && p < _n);
        (*this).set(p, (*this).get(p) + x);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

    int n() const {return (*this)._n;}

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder
//line 4 "answer.cpp"
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<pair<int,int>> pos;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            pos.push_back({i,j});
        }
    }
    sort(pos.begin(), pos.end(), [a](pair<int,int> p, pair<int,int> q) {
        return a[p.first][p.second] < a[q.first][q.second];
    });
    vector<vector<int>> g = [&]() {
        atcoder::dsu uf(h*w);
        vector<vector<int>> g(h*w);
        for (auto [i, j] : pos) {
            cout << i << " " << j << endl;
            for (auto [dx, dy] : dxy) {
                if (i+dx < 0 || i+dx >= h || j+dy < 0 || j+dy >= w) continue;
                int u = i*w+j;
                int v = (i+dx)*w+(j+dy);
                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);
        cout << u << " " << v << " " << l << endl;
        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, int parent_val) -> void {
        int val = a[u/w][u%w];
        seg_query.set(depth[visited[u]], min(val, parent_val));
        cout << u << endl;
        for (int i = 0; i < h*w; i++) cout << seg_query.get(i) << " ";
        cout << endl;
        for (auto [d, id] : query[u]) {
            cout << d << " " << id << endl;
            ans[id] = min(ans[id], seg_query.prod(d+1, h*w));
        }
        for (auto v : g[u]) if (v != parent) self(self, v, u, val);
        seg_query.set(depth[visited[u]], -INF);
    };
    dfs(dfs, 0, -1, INF);
    for (auto x : ans) cout << x << '\n';
}
0