No.2826 Earthwork
タグ : / 解いたユーザー数 13
作問者 :
![🦠みどりむし](https://pbs.twimg.com/profile_images/1258989583968043008/WWF0Yz3c.jpg)
![FplusFplusF](https://pbs.twimg.com/profile_images/1535630966743371776/RVkOr4C0.jpg)
![AngrySadEight](https://pbs.twimg.com/profile_images/1774819988135927808/f4w6hc33.jpg)
問題文
南北に $N$ 個、東西に $N$ 個の、計 $N^2$ 個の区画からなる街があります。
区画 $(i, j) \scriptsize \; (1 \leq i, j \leq N)$ は北から $i$ 行目、西から $j$ 列目の区画であり、この区画の現在の標高は $H_{i, j}$ です。
さて、この街では、それぞれの区画に対して土木工事を予定しています。
区画 $(i, j) \scriptsize \; (1 \leq i, j \leq N)$ での工事の内容は以下です:
- $X_{i, j} = $
-
のとき:切土(のみ)を行い、標高を $0$ 以上の適当な実数だけ減少させる。 - $X_{i, j} = $
+
のとき:盛土(のみ)を行い、標高を $0$ 以上の適当な実数だけ増加させる。 - $X_{i, j} = $
=
のとき:何も行わず、現在の標高を保つ。 - $X_{i, j} = $
?
のとき:切土か盛土かを行い、標高を適当に修正する。
工事後の区画 $(i, j) \scriptsize \; (1 \leq i, j \leq N)$ の標高を $H'_{i, j}$ とします。
ここでさらに、工事後は次の条件がすべて満たされていなければなりません:
$1 \leq i < N$ かつ $1 \leq j \leq N$ なる任意の $2$ 整数 $i, j$ について、$\displaystyle \large \left| \frac{H'_{i, j} + H'_{i + 1, j}}{H_{i, j} + H_{i + 1, j}} \right| \leq A_{i, j}$ である。
$1 \leq i \leq N$ かつ $1 \leq j < N$ なる任意の $2$ 整数 $i, j$ について、$\displaystyle \large \left| \frac{H'_{i, j} + H'_{i, j + 1}}{H_{i, j} + H_{i, j + 1}} \right| \leq B_{i, j}$ である。
ただしこの問題の制約のもとで、適当に工事を行うことによって必ず以上の条件を満たせます。
このとき、$Q$ 個の独立した質問、質問 $1, 2, \dots, Q$ にそれぞれ答えてください:
質問 $k$
行政から区画 $(R_k, C_k)$ に電波塔を立てたいという要望があった。
この電波塔の標高は $E_k$ 以上であることが求められるらしい。適当に工事を行うことで $\large H'_{R_k, C_k} \geq E_k$ とできるだろうか。
入力
入力は、以下の形式で標準入力より与えられる:
$N$ $H_{1,1} \enspace H_{1,2} \enspace \dots \enspace H_{1,N}$ $H_{2,1} \enspace H_{2,2} \enspace \dots \enspace H_{2,N}$ $\vdots$ $H_{N,1} \enspace H_{N,2} \enspace \dots \enspace H_{N,N}$ $X_{1,1}X_{1,2}\dots X_{1,N}$ $X_{2,1}X_{2,2}\dots X_{2,N}$ $\vdots$ $X_{N,1}X_{N,2}\dots X_{N,N}$ $A_{1,1} \enspace A_{1,2} \enspace \dots \enspace A_{1,N}$ $A_{2,1} \enspace A_{2,2} \enspace \dots \enspace A_{2,N}$ $\vdots$ $A_{N-1,1} \enspace A_{N-1,2} \enspace \dots \enspace A_{N-1,N}$ $B_{1,1} \enspace B_{1,2} \enspace \dots \enspace B_{1,N-1}$ $B_{2,1} \enspace B_{2,2} \enspace \dots \enspace B_{2,N-1}$ $\vdots$ $B_{N,1} \enspace B_{N,2} \enspace \dots \enspace B_{N,N-1}$ $Q$ $R_1 \enspace C_1 \enspace E_1$ $R_2 \enspace C_2 \enspace E_2$ $\vdots$ $R_Q \enspace C_Q \enspace E_Q$
出力
次の指示に従って、標準出力へ $Q$ 行出力せよ。
$i \scriptsize \; (1 \leq i \leq Q)$ 行目には、質問 $i$ を肯定するとき Yes
を、そうでないとき No
を出力せよ。
制約
- $2 \leq N \leq 800$
- $1 \leq Q \leq 10^4$
- $\left| H_{i, j} \right| < 2^{30} \scriptsize \; (1 \leq i, j \leq N)$
- $H_{i, j} + H_{i + 1, j} \not= 0 \scriptsize \; (1 \leq i < N \land 1 \leq j \leq N)$
- $H_{i, j} + H_{i, j + 1} \not= 0 \scriptsize \; (1 \leq i \leq N \land 1 \leq j < N)$
- $1 \leq A_{i, j} < 2^{30} \scriptsize \; (1 \leq i < N \land 1 \leq j \leq N)$
- $1 \leq B_{i, j} < 2^{30} \scriptsize \; (1 \leq i \leq N \land 1 \leq j < N)$
- $1 \leq R_{i}, C_{i} \leq N \scriptsize \; (1 \leq i \leq Q)$
- $| E_{i} | < 2^{60} \scriptsize \; (1 \leq i \leq Q)$
- $X_{i,j} \in \{$
-
$, $+
$, $=
$, $?
$\} \scriptsize \; (1 \leq i, j \leq N)$ - $N, Q, H_{i, j}$ は整数 $\scriptsize \; (1 \leq i, j \leq N)$
- $A_{i, j}$ は整数 $\scriptsize (1 \leq i < N \land 1 \leq j \leq N)$
- $B_{i, j}$ は整数 $\scriptsize (1 \leq i \leq N \land 1 \leq j < N)$
- $R_{i}, C_{i}, E_{i}$ は整数 $\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もしくは右上の雲マークをクリックしてアカウントを作成してください。