問題一覧 >
通常問題
No.2826 Earthwork
問題文最終更新日: 2025-02-02 09:26:21
問題文
南北に N 個、東西に N 個の、計 N2 個の区画からなる街があります。
区画 (i,j)(1≤i,j≤N) は北から i 行目、西から j 列目の区画であり、この区画の現在の標高は Hi,j です。
さて、この街では、それぞれの区画に対して土木工事を予定しています。
区画 (i,j)(1≤i,j≤N) での工事の内容は以下です:
- Xi,j=
-
のとき:切土(のみ)を行い、標高を 0 以上の適当な実数だけ減少させる。
- Xi,j=
+
のとき:盛土(のみ)を行い、標高を 0 以上の適当な実数だけ増加させる。
- Xi,j=
=
のとき:何も行わず、現在の標高を保つ。
- Xi,j=
?
のとき:切土か盛土かを行い、標高を適当に修正する。
以上のことに反する工事は行えません。
工事後の区画 (i,j)(1≤i,j≤N) の標高を Hi,j′ とします。
ここでさらに、工事後は次の条件がすべて満たされていなければなりません:
1≤i<N かつ 1≤j≤N なる任意の 2 整数 i,j について、Hi,j+Hi+1,jHi,j′+Hi+1,j′≤Ai,j である。
1≤i≤N かつ 1≤j<N なる任意の 2 整数 i,j について、Hi,j+Hi,j+1Hi,j′+Hi,j+1′≤Bi,j である。
ただしこの問題の制約のもとで、適当に工事を行うことによって必ず以上の条件を満たせます。
このとき、Q 個の独立した質問、質問 1,2,…,Q にそれぞれ答えてください:
質問 k
行政から区画 (Rk,Ck) に電波塔を立てたいという要望があった。
この電波塔の標高は Ek 以上であることが求められるらしい。
適当に工事を行うことで HRk,Ck′≥Ek とできるだろうか。
入力
入力は、以下の形式で標準入力より与えられる:
N
H1,1H1,2…H1,N
H2,1H2,2…H2,N
⋮
HN,1HN,2…HN,N
X1,1X1,2…X1,N
X2,1X2,2…X2,N
⋮
XN,1XN,2…XN,N
A1,1A1,2…A1,N
A2,1A2,2…A2,N
⋮
AN−1,1AN−1,2…AN−1,N
B1,1B1,2…B1,N−1
B2,1B2,2…B2,N−1
⋮
BN,1BN,2…BN,N−1
Q
R1C1E1
R2C2E2
⋮
RQCQEQ
出力
次の指示に従って、標準出力へ Q 行出力せよ。
i(1≤i≤Q) 行目には、質問 i を肯定するとき Yes
を、そうでないとき No
を出力せよ。
制約
- 2≤N≤800
- 1≤Q≤104
- ∣Hi,j∣<230(1≤i,j≤N)
- Hi,j+Hi+1,j=0(1≤i<N∧1≤j≤N)
- Hi,j+Hi,j+1=0(1≤i≤N∧1≤j<N)
- 1≤Ai,j<230(1≤i<N∧1≤j≤N)
- 1≤Bi,j<230(1≤i≤N∧1≤j<N)
- 1≤Ri,Ci≤N(1≤i≤Q)
- ∣Ei∣<260(1≤i≤Q)
- Xi,j∈{
-
, +
, =
, ?
}(1≤i,j≤N)
- N,Q,Hi,j は整数 (1≤i,j≤N)
- Ai,j は整数 (1≤i<N∧1≤j≤N)
- Bi,j は整数 (1≤i≤N∧1≤j<N)
- Ri,Ci,Ei は整数 (1≤i≤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もしくは右上の雲マークをクリックしてアカウントを作成してください。