/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
縦 N マス、横 N マスの N ^ 2 マスからなるマス目があります。 上から i 行目 (1\leq i\leq N) 、左から j 列目 (1\leq j\leq N) のマスをマス (i,j) と呼ぶことにします。
それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。 マス目には合計で M 個のコマが置かれており、k 番目 (1\leq k\leq M) のコマはマス (a _ k,b _ k) に置かれています。
あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。
マス (i,j) に置かれているコマは、次のどれかの条件を満たすコマを取ることができます。
- i 行目に置かれている
- j 列目に置かれている
- i+j=a+b となるようなマス (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) に置かれている
たとえば、マス (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 つです。
入力例 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
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