結果

問題 No.2786 RMQ on Grid Path
ユーザー IkunTeddy
提出日時 2025-02-22 22:52:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 366 ms / 6,000 ms
コード長 3,996 bytes
コンパイル時間 1,998 ms
コンパイル使用メモリ 169,348 KB
実行使用メモリ 93,816 KB
最終ジャッジ日時 2025-02-22 22:52:57
合計ジャッジ時間 11,817 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

//饺子皮是圆皮
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO{
    #define FASTIO
    #define IOSIZE 1000000
    char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
    #ifdef ONLINE_JUDGE
    #define getchar()((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
    #define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif
    #define isdigit(ch)(ch>47&&ch<58)
    #define isspace(ch)(ch<33)
    template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}
    #ifdef _GLIBCXX_STRING
    inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}
    #endif
    template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a);print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}io;template<typename T>Fast_IO&operator>>(Fast_IO&io,T&b){return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO&io,T b){return print(b),io;}
}
#define cin fast_IO::io
#define cout fast_IO::io
#define endl '\n'
//
const int maxn=2e6+10;
const int INF=0x3f3f3f3f;
int n,h,w,q,cnt,Log;
int s[510][510];
int id(int x,int y){return (x-1)*w+y;}
struct Graph{
	int x,y,w;
	bool operator < (const Graph &it)const{
		return w<it.w;
	}
}e[maxn];
struct Edge{
	int v,w,next;
}edge[maxn<<1];
int head[maxn],tot;
void add_edge(int u,int v,int w){
	edge[++tot].v=v;
	edge[tot].w=w;
	edge[tot].next=head[u];
	head[u]=tot;
}
int fa[maxn];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void kruskal(){
	sort(e+1,e+cnt+1);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=cnt;i++){
		int x=e[i].x,y=e[i].y,w=e[i].w;
		if(find(x)!=find(y)){
			fa[find(y)]=find(x);
			add_edge(x,y,w);
			add_edge(y,x,w);
		}
	}
}
int f[maxn][25],mx[maxn][25];
int dep[maxn];
void dfs(int u){
	dep[u]=dep[fa[u]]+1;
	for(int i=1;i<=Log;i++){
		f[u][i]=f[f[u][i-1]][i-1];
		mx[u][i]=max(mx[u][i-1],mx[f[u][i-1]][i-1]);
	}
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v,w=edge[i].w;
		if(v==fa[u])continue ;
		fa[v]=u;
		f[v][0]=u;
		mx[v][0]=w;
		dfs(v);
	}
}
int ask(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int res=0;
	for(int i=Log;i>=0;i--)if(dep[f[x][i]]>=dep[y])res=max(res,mx[x][i]),x=f[x][i];
	if(x==y)return res;
	for(int i=Log;i>=0;i--)if(f[x][i]!=f[y][i])res=max(res,max(mx[x][i],mx[y][i])),x=f[x][i],y=f[y][i];
	res=max(res,max(mx[x][0],mx[y][0]));
	return res;
}
int main(){
	cin>>h>>w;
	n=h*w;
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)cin>>s[i][j];
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(i!=1)e[++cnt]={id(i,j),id(i-1,j),max(s[i][j],s[i-1][j])};
			if(j!=1)e[++cnt]={id(i,j),id(i,j-1),max(s[i][j],s[i][j-1])};
		}
	}
	kruskal();
	memset(fa,0,sizeof(fa));
	Log=__lg(n);
	dfs(1);
	cin>>q;
	while(q--){
		int x1,y1,x2,y2,x,y;
		cin>>x1>>y1>>x2>>y2;
		x=id(x1,y1),y=id(x2,y2);
		if(x==y){
			cout<<0<<'\n';
			continue ;
		}
		cout<<ask(x,y)<<'\n';
	}
	
	return 0;
}
0