102606: [AtCoder]ABC260 G - Scalene Triangle Area
Description
Score : $600$ points
Problem Statement
We have an $N \times N$ grid. The square at the $i$-th row from the top and $j$-th column from the left in this grid is called $(i,j)$.
Each square of the grid has at most one piece.
The state of the grid is given by $N$ strings $S_i$:
- if the $j$-th character of $S_i$ is
O
, then $(i,j)$ has a piece on it; - if the $j$-th character of $S_i$ is
X
, then $(i,j)$ has no piece on it.
You are given an integer $M$. Using this $M$, we define that a piece $P$ placed at $(s,t)$ covers a square $(u,v)$ if all of the following conditions are satisfied:
- $s \le u \le N$
- $t \le v \le N$
- $(u - s) + \frac{(v - t)}{2} < M$
For each of $Q$ squares $(X_i,Y_i)$, find how many pieces cover the square.
Constraints
- $N$, $M$, $X_i$, $Y_i$, and $Q$ are integers.
- $1 \le N \le 2000$
- $1 \le M \le 2 \times N$
- $S_i$ consists of
O
andX
. - $1 \le Q \le 2 \times 10^5$
- $1 \le X_i,Y_i \le N$
Input
Input is given from Standard Input in the following format:
$N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$ $Q$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_Q$ $Y_Q$
Output
Print $Q$ lines.
The $i$-th line ( $1 \le i \le Q$ ) should contain the number of pieces that covers $(X_i,Y_i)$ as an integer.
Sample Input 1
4 2 OXXX XXXX XXXX XXXX 6 1 1 1 4 2 2 2 3 3 1 4 4
Sample Output 1
1 1 1 0 0 0
Only Square $(1,1)$ contains a piece, which covers the following #
squares:
#### ##.. .... ....
Sample Input 2
5 10 OOOOO OOOOO OOOOO OOOOO OOOOO 5 1 1 2 3 3 4 4 2 5 5
Sample Output 2
1 6 12 8 25
Sample Input 3
8 5 OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO 6 7 2 8 1 4 5 8 8 3 4 1 7
Sample Output 3
5 3 9 14 5 3
Input
题意翻译
我们有一个 $N\times N$ 的方阵,由 XO 组成,对于一个位于 $(s,t)$ 的 O,他可以控制的范围是 $(u,v)$,满足: - $s\le u.$ - $t\le v.$ - $(u-s)+\dfrac{(v-t)}{2}<M$。 给定 $N,M,Q$ 和 $Q$ 次询问 $X_i,Y_i$,询问这个位置被几个 O 控制。 翻译者:@Gemini7XOutput
问题描述
我们有一个$N \times N$的网格。这个网格中从上数第$i$行、从左数第$j$列的正方形称为$(i,j)$。
- 如果$S_i$的第$j$个字符为
O
,那么$(i,j)$上有一个棋子; - 如果$S_i$的第$j$个字符为
X
,那么$(i,j)$上没有棋子。
给你一个整数$M$。使用这个$M$,我们定义一个放在$(s,t)$的棋子覆盖正方形$(u,v)$,当且仅当满足以下条件:
- $s \le u \le N$
- $t \le v \le N$
- $(u - s) + \frac{(v - t)}{2} < M$
对于每个正方形$(X_i,Y_i)$,找出有多少棋子覆盖了这个正方形。
约束
- $N$,$M$,$X_i$,$Y_i$和$Q$是整数。
- $1 \le N \le 2000$
- $1 \le M \le 2 \times N$
- $S_i$由
O
和X
组成。 - $1 \le Q \le 2 \times 10^5$
- $1 \le X_i,Y_i \le N$
输入
输入从标准输入按以下格式给出:
$N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$ $Q$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_Q$ $Y_Q$
输出
输出$Q$行。
第$i$行($1 \le i \le Q$)应包含覆盖$(X_i,Y_i)$的棋子数量。
样例输入1
4 2 OXXX XXXX XXXX XXXX 6 1 1 1 4 2 2 2 3 3 1 4 4
样例输出1
1 1 1 0 0 0
只有正方形$(1,1)$包含一个棋子,它覆盖了以下#
正方形:
####
##..
....
....
样例输入2
5 10 OOOOO OOOOO OOOOO OOOOO OOOOO 5 1 1 2 3 3 4 4 2 5 5
样例输出2
1 6 12 8 25
样例输入3
8 5 OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO 6 7 2 8 1 4 5 8 8 3 4 1 7
样例输出3
5 3 9 14 5 3