結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー vulestamenkovic
提出日時 2026-01-19 19:28:06
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 356 ms / 6,000 ms
コード長 1,876 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,165 ms
コンパイル使用メモリ 229,544 KB
実行使用メモリ 24,316 KB
最終ジャッジ日時 2026-01-19 19:28:19
合計ジャッジ時間 11,602 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define int long long
#define MAXN (int)505
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,m,a[MAXN][MAXN],p[MAXN*MAXN],c[MAXN*MAXN],s[MAXN*MAXN],vv[MAXN][MAXN],d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
pii r[MAXN*MAXN];
int k(int i,int j){
    return m*i+j;
}int find(int x){
    return p[x]=(x==p[x]?x:find(p[x]));
}
void unite(int u,int v){
    u=find(u);
    v=find(v);
    if(u==v){return;}
    if(s[u]<s[v]){
        swap(u,v);
    }
    c[u]=max(c[u],c[v]);
    r[v]={u,c[u]};
    s[u]+=s[v];
    p[v]=u;
}
void solve() {
    cin>>n>>m;
    priority_queue<tuple<int,int,int>>pq;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            p[k(i,j)]=r[k(i,j)].fi=k(i,j);
            s[k(i,j)]=1;
            cin>>a[i][j];
            c[k(i,j)]=r[k(i,j)].se=a[i][j];
            pq.emplace(-a[i][j],i,j);
        }
    }
    while(!pq.empty()){
        int x,u,v;
        tie(x,u,v)=pq.top();pq.pop();
        vv[u][v]=1;
        for(int i=0;i<4;i++){
            int xx=u+d[i][0],yy=v+d[i][1];
            if(xx>=0&&yy>=0&&xx<n&&yy<m&&vv[xx][yy]){
                unite(k(u,v),k(xx,yy));
            }
        }
    }
    int q;cin>>q;
    while(q--){
        int x,y,u,v;cin>>x>>y>>u>>v;--u;--v;--x;--y;
        map<int,int>l;
        int z=k(u,v),o=1e9;
        l[z]=a[z/m][z%m];
        while(r[z].fi!=z){
            l[r[z].fi]=r[z].se;
            z=r[z].fi;
        }
        z=k(x,y);
        if(l[z]){
            o=min(o,max(l[z],a[z/m][z%m]));
        }
        while(r[z].fi!=z){
            if(l[r[z].fi]){
                o=min(o,max(l[r[z].fi],r[z].se));
            }
            z=r[z].fi;
        }
        cout<<o<<'\n';
    }
}
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int32_t T=1;//cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}
0