103775: [Atcoder]ABC377 F - Avoid Queen Attack

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:6 Solved:0

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)$,$(

加入题单

上一题 下一题 算法标签: