103775: [Atcoder]ABC377 F - Avoid Queen Attack
Description
Score : $550$ points
Problem Statement
There is a grid of $N^2$ squares with $N$ rows and $N$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top $(1\leq i\leq N)$ and $j$-th column from the left $(1\leq j\leq N)$.
Each square is either empty or has a piece placed on it. There are $M$ pieces placed on the grid, and the $k$-th $(1\leq k\leq M)$ piece is placed on square $(a_k,b_k)$.
You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.
A piece placed on square $(i,j)$ can capture pieces that satisfy any of the following conditions:
- Placed in row $i$
- Placed in column $j$
- Placed on any square $(a,b)\ (1\leq a\leq N,1\leq b\leq N)$ where $i+j=a+b$
- Placed on any square $(a,b)\ (1\leq a\leq N,1\leq b\leq N)$ where $i-j=a-b$
For example, a piece placed on square $(4,4)$ can capture pieces placed on the squares shown in blue in the following figure:
How many squares can you place your piece on?
Constraints
- $1\leq N\leq10^9$
- $1\leq M\leq10^3$
- $1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)$
- $(a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$
Output
Print the number of empty squares where you can place your piece without it being captured by any existing pieces.
Sample Input 1
8 6 1 4 2 1 3 8 4 5 5 2 8 3
Sample Output 1
2
The existing pieces can capture pieces placed on the squares shown in blue in the following figure:
Therefore, you can place your piece on only two squares: squares $(6,6)$ and $(7,7)$.
Sample Input 2
1000000000 1 1 1
Sample Output 2
999999997000000002
Out of $10^{18}$ squares, the squares that cannot be used are: squares in row $1$, squares in column $1$, and squares $(1,1)$, $(2,2)$, $\ldots$, $(10^9,10^9)$, totaling $3\times10^9-2$ squares.
Note that the answer may be $2^{32}$ or greater.
Sample Input 3
20 10 1 4 7 11 7 15 8 10 11 6 12 5 13 1 15 2 20 10 20 15
Sample Output 3
77
Output
得分:550分
问题陈述
有一个由$N^2$个方格组成的网格,有$N$行和$N$列。 用$(i,j)$表示从顶部开始的第$i$行$(1\leq i\leq N)$和从左边开始的第$j$列$(1\leq j\leq N)$的方格。
每个方格要么为空,要么放置了一个棋子。 网格上有$M$个棋子,第$k$个$(1\leq k\leq M)$个棋子放在方格$(a_k,b_k)$上。
你想要将你的棋子放在一个空方格上,以使它不能被任何现有的棋子捕获。
放在方格$(i,j)$上的棋子可以捕获满足以下任一条件的棋子:
- 放在第$i$行
- 放在第$j$列
- 放在任一方格$(a,b)\ (1\leq a\leq N,1\leq b\leq N)$,其中$i+j=a+b$
- 放在任一方格$(a,b)\ (1\leq a\leq N,1\leq b\leq N)$,其中$i-j=a-b$
例如,放在方格$(4,4)$上的棋子可以捕获如下图蓝色方格上放置的棋子:
你可以将你的棋子放在多少个方格上?
约束条件
- $1\leq N\leq10^9$
- $1\leq M\leq10^3$
- $1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)$
- $(a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)$
- 所有输入值都是整数。
输入
输入从标准输入以下格式给出:
$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$
输出
打印你可以放置棋子而不会被任何现有棋子捕获的空方格的数量。
示例输入 1
8 6 1 4 2 1 3 8 4 5 5 2 8 3
示例输出 1
2
现有的棋子可以捕获放在如下图蓝色方格上的棋子:
因此,你只能将你的棋子放在两个方格上:方格$(6,6)$和$(7,7)$。
示例输入 2
1000000000 1 1 1
示例输出 2
999999997000000002
在$10^{18}$个方格中,不能使用的方格有:第$1$行的方格,第$1$列的方格,以及方格$(1,1)$,$(