← 返回题目列表

AtCoder · abc377_f

I. 避免女王攻击

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

有一个网格 N^2 方块与 N 行和 N 列。 让 (i,j) 表示位于 i从顶部算起的第行 (1\leq i\leq N) 和 j左起第 列 (1\leq j\leq N).

每个方格要么是空的,要么上面放置了一个棋子。 有 M 棋子放置在网格上,并且 k-th (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), (2,2), \ldots, (10^9,10^9),总计 3\times10^9-2 方块。

请注意,答案可能是 2^{32} 或更大。


示例输入 3

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

示例输出 3

77