No.2826 Earthwork
タグ : / 解いたユーザー数 14
作問者 :
みどりむし🦠
/ テスター :
FplusFplusF
Problem Statement
There is a town consisting of $N$ sections from north to south and $N$ sections from east to west, for a total of $N^2$ sections.
Section $(i, j) \scriptsize \; (1 \leq i, j \leq N)$ is the section in the $i$-th row from the north and the $j$-th column from the west, and the current elevation of this section is $H_{i, j}$.
Now, this town plans to carry out civil engineering work on each of the sections.
The work on section $(i, j) \scriptsize \; (1 \leq i, j \leq N)$ is as follows:
- If $X_{i, j} = $
-: perform cutting (only), decreasing the elevation by some real number that is at least $0$. - If $X_{i, j} = $
+: perform filling (only), increasing the elevation by some real number that is at least $0$. - If $X_{i, j} = $
=: do nothing, keeping the current elevation. - If $X_{i, j} = $
?: perform either cutting or filling, modifying the elevation as desired.
Let $H'_{i, j}$ be the elevation of section $(i, j) \scriptsize \; (1 \leq i, j \leq N)$ after the work.
Furthermore, all of the following conditions must be satisfied after the work:
For any $2$ integers $i, j$ such that $1 \leq i < N$ and $1 \leq j \leq N$, $\displaystyle \large \left| \frac{H'_{i, j} + H'_{i + 1, j}}{H_{i, j} + H_{i + 1, j}} \right| \leq A_{i, j}$ holds.
For any $2$ integers $i, j$ such that $1 \leq i \leq N$ and $1 \leq j < N$, $\displaystyle \large \left| \frac{H'_{i, j} + H'_{i, j + 1}}{H_{i, j} + H_{i, j + 1}} \right| \leq B_{i, j}$ holds.
Under the constraints of this problem, the above conditions can always be satisfied by performing the work appropriately.
Answer each of the $Q$ independent queries, Queries $1, 2, \dots, Q$:
Query $k$
The government has requested to build a radio tower on section $(R_k, C_k)$.
The elevation of this radio tower is apparently required to be at least $E_k$.Is it possible to make $\large H'_{R_k, C_k} \geq E_k$ by performing the work appropriately?
Input
The input is given from standard input in the following format:
$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$
Output
Following the instructions below, print $Q$ lines to standard output.
On line $i \scriptsize \; (1 \leq i \leq Q)$, print Yes if the answer to Query $i$ is affirmative, and No otherwise.
Constraints
- $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}$ are integers $\scriptsize \; (1 \leq i, j \leq N)$
- $A_{i, j}$ are integers $\scriptsize (1 \leq i < N \land 1 \leq j \leq N)$
- $B_{i, j}$ are integers $\scriptsize (1 \leq i \leq N \land 1 \leq j < N)$
- $R_{i}, C_{i}, E_{i}$ are integers $\scriptsize (1 \leq i \leq Q)$
Sample
Sample Input/Output 1
Input
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
Output
No Yes Yes No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。