問題一覧 > 通常問題

No.2826 Earthwork

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 14
作問者 : みどりむし🦠 / テスター : FplusFplusF viral8 achapi 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 10934 / 自分の提出
問題文最終更新日: 2025-02-02 09:26:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 438 (順位表) の他の問題:

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.
Work that violates the above cannot be performed.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。