出口 \(i\) が燃え始める時刻を \(T_{i}\) としたとき、人 \(j\) が助かる条件は、\(\displaystyle \min_{1\leq i\leq N}(|A_{i} - X_{j}| + |B_{i} - Y_{j}| - T_{i})\) が \(0\) 未満であること同値です。

もし、この値が \(0\) 以上なら、最短距離でどの出口に行ってもたどり着いたタイミングで出口は燃えています。

この値が \(0\) 未満である出口に最短距離で向かっているタイミングで人 \(j\) が燃えるとすると、その最短距離で燃え広がることで、出口 \(i\) の燃え始める時刻を \(T_{i}\) より小さくできてしまうため矛盾が生じます。

この値は、任意の \(i\) に対する \(T_{i}\) がわかっているとき、以下の問題を \(4\) 回解くことで求めることができます。

全ての \(j\) に対して、以下の値を求めてください。

• \(X_{j}\leq A_{i}\) かつ \(Y_{j}\leq B_{i}\) を満たすすべての \(i\) に対する \(A_{i} - X_{j} + B_{i} - Y_{j} - T_{i}\)

区間 min の segment tree を持ちながら \(Y_{j}, B_{i}\) の大きい順に見て、出口のクエリのときには segment tree の \(A_{i}\) 番目を \(A_{i} + B_{i} - T_{i}\) に更新し、人のクエリのときには、segment tree の \(X_{j}\) 番目以降の最小値を取得すればいいです。

あとは任意の \(i\) に対する \(T_{i}\) がわかればいいですが、これは任意の \(i\) に対して、 \(\displaystyle \min_{1\leq k\leq M}(|A_{i} - C_{k}| + |B_{i} - D_{k}| )\) を求めれることができればわかるので、全く同じ問題に帰着できます。(上記の問題を解く関数を作ることによって、実装の手間が半分になります。)