問題一覧 > 通常問題

No.2826 Earthwork

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : 🦠みどりむし🦠みどりむし / テスター : FplusFplusFFplusFplusF viral8viral8 achapiachapi 👑 AngrySadEightAngrySadEight
1 ProblemId : 10934 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-02 09:26:21

問題文

南北に NN 個、東西に NN 個の、計 N2N^2 個の区画からなる街があります。
区画 (i,j)(1i,jN)(i, j) \scriptsize \; (1 \leq i, j \leq N) は北から ii 行目、西から jj 列目の区画であり、この区画の現在の標高Hi,jH_{i, j} です。

さて、この街では、それぞれの区画に対して土木工事を予定しています。

区画 (i,j)(1i,jN)(i, j) \scriptsize \; (1 \leq i, j \leq N) での工事の内容は以下です:

  • Xi,j=X_{i, j} = - のとき:切土(のみ)を行い、標高を 00 以上の適当な実数だけ減少させる。
  • Xi,j=X_{i, j} = + のとき:盛土(のみ)を行い、標高を 00 以上の適当な実数だけ増加させる。
  • Xi,j=X_{i, j} = = のとき:何も行わず、現在の標高を保つ。
  • Xi,j=X_{i, j} = ? のとき:切土か盛土かを行い、標高を適当に修正する。
以上のことに反する工事は行えません。

工事後の区画 (i,j)(1i,jN)(i, j) \scriptsize \; (1 \leq i, j \leq N) の標高を Hi,jH'_{i, j} とします。

ここでさらに、工事後は次の条件がすべて満たされていなければなりません:

  • 1i<N1 \leq i < N かつ 1jN1 \leq j \leq N なる任意の 22 整数 i,ji, j について、Hi,j+Hi+1,jHi,j+Hi+1,jAi,j\displaystyle \large \left| \frac{H'_{i, j} + H'_{i + 1, j}}{H_{i, j} + H_{i + 1, j}} \right| \leq A_{i, j} である。

  • 1iN1 \leq i \leq N かつ 1j<N1 \leq j < N なる任意の 22 整数 i,ji, j について、Hi,j+Hi,j+1Hi,j+Hi,j+1Bi,j\displaystyle \large \left| \frac{H'_{i, j} + H'_{i, j + 1}}{H_{i, j} + H_{i, j + 1}} \right| \leq B_{i, j} である。

ただしこの問題の制約のもとで、適当に工事を行うことによって必ず以上の条件を満たせます。

このとき、QQ 個の独立した質問、質問 1,2,,Q1, 2, \dots, Q にそれぞれ答えてください:

質問 kk

行政から区画 (Rk,Ck)(R_k, C_k) に電波塔を立てたいという要望があった。
この電波塔の標高は EkE_k 以上であることが求められるらしい。

適当に工事を行うことで HRk,CkEk\large H'_{R_k, C_k} \geq E_k とできるだろうか。

入力

入力は、以下の形式で標準入力より与えられる:

NN
H1,1H1,2H1,NH_{1,1} \enspace H_{1,2} \enspace \dots \enspace H_{1,N}
H2,1H2,2H2,NH_{2,1} \enspace H_{2,2} \enspace \dots \enspace H_{2,N}
\vdots
HN,1HN,2HN,NH_{N,1} \enspace H_{N,2} \enspace \dots \enspace H_{N,N}
X1,1X1,2X1,NX_{1,1}X_{1,2}\dots X_{1,N}
X2,1X2,2X2,NX_{2,1}X_{2,2}\dots X_{2,N}
\vdots
XN,1XN,2XN,NX_{N,1}X_{N,2}\dots X_{N,N}
A1,1A1,2A1,NA_{1,1} \enspace A_{1,2} \enspace \dots \enspace A_{1,N}
A2,1A2,2A2,NA_{2,1} \enspace A_{2,2} \enspace \dots \enspace A_{2,N}
\vdots
AN1,1AN1,2AN1,NA_{N-1,1} \enspace A_{N-1,2} \enspace \dots \enspace A_{N-1,N}
B1,1B1,2B1,N1B_{1,1} \enspace B_{1,2} \enspace \dots \enspace B_{1,N-1}
B2,1B2,2B2,N1B_{2,1} \enspace B_{2,2} \enspace \dots \enspace B_{2,N-1}
\vdots
BN,1BN,2BN,N1B_{N,1} \enspace B_{N,2} \enspace \dots \enspace B_{N,N-1}
QQ
R1C1E1R_1 \enspace C_1 \enspace E_1
R2C2E2R_2 \enspace C_2 \enspace E_2
\vdots
RQCQEQR_Q \enspace C_Q \enspace E_Q

出力

次の指示に従って、標準出力へ QQ 行出力せよ。
i(1iQ)i \scriptsize \; (1 \leq i \leq Q) 行目には、質問 ii を肯定するとき Yes を、そうでないとき No を出力せよ。

制約

  • 2N8002 \leq N \leq 800
  • 1Q1041 \leq Q \leq 10^4
  • Hi,j<230(1i,jN)\left| H_{i, j} \right| < 2^{30} \scriptsize \; (1 \leq i, j \leq N)
  • Hi,j+Hi+1,j0(1i<N1jN)H_{i, j} + H_{i + 1, j} \not= 0 \scriptsize \; (1 \leq i < N \land 1 \leq j \leq N)
  • Hi,j+Hi,j+10(1iN1j<N)H_{i, j} + H_{i, j + 1} \not= 0 \scriptsize \; (1 \leq i \leq N \land 1 \leq j < N)
  • 1Ai,j<230(1i<N1jN)1 \leq A_{i, j} < 2^{30} \scriptsize \; (1 \leq i < N \land 1 \leq j \leq N)
  • 1Bi,j<230(1iN1j<N)1 \leq B_{i, j} < 2^{30} \scriptsize \; (1 \leq i \leq N \land 1 \leq j < N)
  • 1Ri,CiN(1iQ)1 \leq R_{i}, C_{i} \leq N \scriptsize \; (1 \leq i \leq Q)
  • Ei<260(1iQ)| E_{i} | < 2^{60} \scriptsize \; (1 \leq i \leq Q)
  • Xi,j{X_{i,j} \in \{ -,, + ,, = ,, ? }(1i,jN)\} \scriptsize \; (1 \leq i, j \leq N)
  • N,Q,Hi,jN, Q, H_{i, j} は整数 (1i,jN)\scriptsize \; (1 \leq i, j \leq N)
  • Ai,jA_{i, j} は整数 (1i<N1jN)\scriptsize (1 \leq i < N \land 1 \leq j \leq N)
  • Bi,jB_{i, j} は整数 (1iN1j<N)\scriptsize (1 \leq i \leq N \land 1 \leq j < N)
  • Ri,Ci,EiR_{i}, C_{i}, E_{i} は整数 (1iQ)\scriptsize (1 \leq i \leq Q)

サンプル

入出力例1
入力
4
-8 -7 -6 -5
-1 -2 -3 -4
0 1 2 3
7 6 5 4
-+=?
+=?-
=?-+
?-+=
1 2 3 4
5 6 7 8
9 10 11 12
1 5 9
2 6 10
3 7 11
9 8 12
4
1 3 0
1 4 20
4 1 40
2 3 50
出力
No
Yes
Yes
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。