Finding the answer to each query

First, let us fix an \(i\) \((1\leq i\leq Q)\) and consider how we can find the answer for the \(i\)-th query.

For a path from the \(Y_i\)-th floor in block \((A_i,B_i)\) to the \(Z_i\)-th floor in block \((C_i,D_i)\), let \(X\) be the lowest floor passed through (in any building). Here, note that \(X\leq Y_i\) and \(X\leq Z_i\). Because using a walkways does not change the floor, he needs to go down at least \((Y_i-X)\) times and go up at least \((Z_i-X)\) times. Thus, he uses stairs at least \((Y_i+Z_i-2X)\) times. Conversely, he can achieve this count by moving as follows:

• Move down from the \(Y_i\)-th to \(X\)-th floor in the building in block \((A_i,B_i)\).
• Use walkways to move between buildings just as in the original path, except that those on the \(X\)-th floors are used.
• Move up from the \(X\)-th to \(Z_i\)-th floor in the building in block \((C_i,D_i)\).

Such a journey is always possible. Note that all the moves in the path are performed in the \(X\)-th floor or above, and for \(X_1<X_2\), if one can travel between two buildings via the \(X_2\)-th floor, then doing so via the \(X_1\)-th floor is also possible.
One can consider such a path for a path that minimizes the number of usage of stairs, so there exists a path that minimizes the number of uses of stairs that satisfies the following conditions. Here, \(1\leq X'\leq \min(Y_i,Z_i)\), where \(\min(Y_i,Z_i)\) denotes the smallest value between \(Y_i\) and \(Z_i\).

• Move down from the \(Y_i\)-th to \(X'\)-th floor in the building in block \((A_i,B_i)\).
• Use walkways to move from the building in block \((A_i,B_i)\) to that in block \((C_i,D_i)\) via (adjacent) buildings with at least \(X'\) floors.
• Move up from the \(X'\)-th to \(Z_i\)-th floor in the building in block \((C_i,D_i)\).

Since stairs are used \((Y_i+Z_i-2X')\) times in this path, the number of uses of stairs is minimized when \(X'\) maximized. Therefore, the answer to the problem can be represented as \((Y_i+Z_i-2\min(M_i,\min(Y_i,Z_i)))\), where \(M_i\) is the maximum positive integer such that:

• one can travel from the building in block \((A_i,B_i)\) to that in block \((C_i, D_i)\) via walkways between buildings with at least \(M_i\) floors.

\(M_i\) can be found using a Disjoint Set Union (DSU). Sort the pairs of adjacent buildings in ascending order of the height of the shorter of them. Join the buildings in the order of that sorted sequence, then \(M_i\) is the height (of the shorter of the buildings in the pair) when the buildings in blocks \((A_i,B_i)\) and \((C_i,D_i)\) belong to the same connected component for the first time.

Solution for the original problem

It is sufficient to do it for each \(i=1,2\ldots, Q\). There are multiple ways to do this; here we introduce an approached based on parallel binary search.

For each \(i=1,2\ldots, Q\), initially set \(L_i=1\) and \(R_i=\max(F_{i,j})+1\). Here, \(\max(F_{i,j})\) denotes the maximum height of a building. Then, repeat the following until \(R_i-L_i\) becomes \(1\) for all \(i\). Here we use the aforementioned sequence of the buildings again.

• Initialize the DSU.
• For each \(i=1,2,\ldots,Q\), compute \(m_i=\left\lfloor \frac{L_i+R_i}{2}\right\rfloor\).
• Merge the DSU according to the sequence of buildings. During the process, when all the buildings of height at least \(H\) is merged, for each \(i\) with \(m_i=h\), check if buildings in blocks \((A_i,B_i)\) and \((C_i,D_i)\) belong to the same connected component. If it does, let \(L_i=m_i\); otherwise, let \(R_i=m_i\).

The sought value \(M_i\) is the final value of \(L_i\). Here, the computational complexity is \(O(HW\log(HW)+(Q+HW)\alpha(HW)\log(\max(F_{i,j})))\), where \(\alpha(n)\) is the inverse Ackerman function.
This is fast enough under the constraints of the problem, so the problem has been solved.

Alternatively, one can use so-called “merge technique.”

Sample code in C++:
(Note: to simplify the code, the complexity has worsened by \(O(\max(F_{i,j})\log(\max(F_{i,j})))\), but it is fine under the constraints of this problem.)

#include <bits/stdc++.h>
#include <atcoder/dsu>

using namespace std;
using namespace atcoder;

#define H 500
#define W 500
#define Q (int)2e+5
#define F (int)1e+6


int main(void){
	int h,w,q;
	int f[H][W];
	int a[Q],b[Q],y[Q],c[Q],d[Q],z[Q],l[Q],r[Q];
	vector<pair<int,int> >e[F+1];
	vector<int>check[F+1];

	cin>>h>>w;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin>>f[i][j];
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>a[i]>>b[i]>>y[i]>>c[i]>>d[i]>>z[i];
		a[i]--,b[i]--,c[i]--,d[i]--;
	}

	for(int i=0;i<h-1;i++)for(int j=0;j<w;j++)e[min(f[i][j],f[i+1][j])].push_back({i*w+j,(i+1)*w+j});
	for(int i=0;i<h;i++)for(int j=0;j<w-1;j++)e[min(f[i][j],f[i][j+1])].push_back({i*w+j,i*w+(j+1)});
	for(int i=0;i<q;i++)l[i]=1,r[i]=F+1;

	while(true){
		bool flag=true;
		for(int i=0;i<=F;i++)check[i].clear();
		for(int i=0;i<q;i++){
			if(r[i]-l[i]>1){
				check[(l[i]+r[i])/2].push_back(i);
				flag=false;
			}
		}
		if(flag)break;

		dsu uf(h*w);
		for(int i=F;i>=0;i--){
			int sz=e[i].size();
			for(int j=0;j<sz;j++)uf.merge(e[i][j].first,e[i][j].second);
			sz=check[i].size();
			for(int j=0;j<sz;j++){
				int idx_s=a[check[i][j]]*w+b[check[i][j]];
				int idx_t=c[check[i][j]]*w+d[check[i][j]];
				if(uf.same(idx_s,idx_t))l[check[i][j]]=i;
				else r[check[i][j]]=i;
			}
		}
	}

	for(int i=0;i<q;i++)cout<<(y[i]+z[i]-2*min(l[i],min(y[i],z[i])))<<endl;
	return 0;
}