No.1141 Ta Grid
レベル :
/ AI推定難易度 : 1200
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 211
作問者 :
fuppy_kyopro
/ テスター :
omochana2
タグ : / 解いたユーザー数 211
作問者 :
fuppy_kyopro
/ テスター :
omochana2
問題文最終更新日: 2019-10-16 22:43:30
English (AI translation)
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 259
(順位表)
の他の問題:
Problem Statement
There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i, j)$.
Each of these cells contains one non-negative integer. The cell $(i, j)$ contains $A_{i,j}$.
You are given $Q$ queries, each consisting of two integers $(r_i, c_i)$. Answer each query. The $i$-th query is as follows.
- When all cells in the $r_i$-th row from the top or the $c_i$-th column from the left of the grid are painted black, find the product of the numbers written in the $(H-1) \times (W-1)$ cells that are not painted.
Also, note that queries do not affect other queries. That is, cells painted black in one query do not remain painted afterward.
Input
$H\ W$
$A_{1,1}~A_{1,2}~...~A_{1,W}$
:
$A_{H,1}~A_{H,2}~...~A_{H,W}$
$Q$
$r_1~c_1$
:
$r_Q~c_Q$
- $2 \le H,W \le 10^5$
- $4 \le H \times W \le 10^5$
- $0 \le A_{i,j} \le 10^9$
- $1 \le Q \le 5 \times 10^4$
- $1 \le r_i \le H$
- $1 \le c_i \le W$
- All inputs are integers.
Output
Output $Q$ lines. On the $i$-th line, output the answer to the $i$-th query. Print a newline at the end.
Sample
Sample 1
Input
2 2 4 3 7 9 1 1 1
Output
9
Sample 2
Input
3 3 7 4 2 9 5 2 9 6 5 2 1 1 3 3
Output
300 1260
Sample 3
Input
3 4 6 8 6 8 3 4 2 9 2 8 6 3 3 3 2 1 2 1 3
Output
15552 1944 5184
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。