結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー OTTFF
提出日時 2024-06-15 10:04:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,195 ms / 6,000 ms
コード長 5,069 bytes
コンパイル時間 2,610 ms
コンパイル使用メモリ 219,108 KB
最終ジャッジ日時 2025-02-21 22:36:47
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
struct UF {
  int n;
  vector<int> fa;
  UF(int n_=0):n(n_),fa(n_) { 
    for(int i=0;i<n;i++) fa[i]=i;
  }
  void init(int n_) {
    n=n_; fa.assign(n,0);
    for(int i=0;i<n;i++) fa[i]=i;
  }
  int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]); }
  bool same(int x,int y) { return find(x)==find(y); }
  bool merge(int x,int y) {
    x=find(x); y=find(y);
    if(x==y) return false;
    fa[x]=y;
    return true;
  }
  vector<vector<int>> getgrps() {
    vector<int> id(n, -1);
    vector<vector<int> > grps;
    for (int i = 0; i < n; i++) {
      if (id[find(i)] == -1) {
        id[find(i)] = grps.size();
        grps.emplace_back();
      }
      grps[id[find(i)]].push_back(i);
    }
    return grps;
  }
};
template<typename Func> struct YCombinatorResult {
  Func func;
  template<typename T>
  explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
  template<class ...Args> decltype(auto) operator()(Args &&...args) {
    return func(std::ref(*this), std::forward<Args>(args)...);
  }
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
  return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void solve() {
  int n, m; cin >> n >> m;
  int nv = n * m;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  auto getid = [&](int x, int y) -> int {
    return x * m + y;
  };
  // auto getpos = [&](int id) -> PII {
  //   return {id / m, id % m};
  // };

  int q; cin >> q;
  vector<vector<PII>> qs(nv);
  int stx, sty, edx, edy;
  int u, v;
  for (int i = 0; i < q; i++) {
    cin >> stx >> sty >> edx >> edy;
    stx--; sty--; edx--; edy--;
    u = getid(stx, sty); 
    v = getid(edx, edy);

    qs[u].push_back({v, i});
    qs[v].push_back({u, i});
  }

  vector<PII> rk;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      rk.push_back({i, j});
    }
  }
  sort(rk.begin(), rk.end(), [&](const PII& x, const PII& y){
    return a[x.first][x.second] < a[y.first][y.second];
  });
  
  vector<set<int>> ses(nv);
  for (int i = 0; i < nv; i++) {
    ses[i].insert(i);
  }

  vector<int> ans(q);

  auto smart_merge = [&](int u, int v, int nans) {
    // cerr << "merging " << u << ' ' << v << ' ' << nans << endl;

    // merge qs:
    int f = 0;
    // always merge u into v
    if (qs[u].size() > qs[v].size()) {
      f = 1;
      swap(u, v);
    }
    for (auto&& [qv, id] : qs[u]) {
      // cerr << " q " << qv << ' ' << id << endl;
      if (ses[v].count(qv)) {
        // cerr << "addressed!" << endl;
        ans[id] = nans;
      } else {
        qs[v].push_back({qv, id});
      }
    }
    if (f) {
      f = 0;
      swap(qs[u], qs[v]);
      swap(u, v);
    }

    // merge ses:
    if (ses[u].size() > ses[v].size()) {
      f = 1;
      swap(u, v);
    }

    for (int val : ses[u]) {
      // cerr << " v " << val << ' ';
      ses[v].insert(val);
    }
    // cerr << endl;

    if (f) {
      swap(ses[u], ses[v]);
      swap(u, v);
    }

    // cerr << "merged " << u << ' ' << v << endl;
    // for (auto&& [qv, id] : qs[v]) {
    //   cerr << qv << ' ' << id << endl;
    // }
    // cerr << "vals : ";
    // for (int val : ses[v]) {
    //   cerr << val << ' ';
    // }
    // cerr << '\n' << endl;
  };

  vector<vector<int>> vis(n, vector<int>(m));
  UF uf(nv);
  for (auto&& [x, y] : rk) {
    vis[x][y] = 1;
    int id = getid(x, y);
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i], ny = y + dy[i];

      if (nx < 0 || n <= nx || ny < 0 || m <= ny || !vis[nx][ny]) continue;

      int idv = uf.find(getid(nx, ny));
      if (uf.merge(idv, id)) {
        smart_merge(idv, id, a[x][y]);
      }
    }
  }

  for (int i = 0; i < q; i++) {
    cout << ans[i] << '\n';
  }
}

int main() {
  int t = 1; 
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
0