C - Avoid Knight Attack Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

縦 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+2,j+1) に置かれている
  • マス (i+1,j+2) に置かれている
  • マス (i-1,j+2) に置かれている
  • マス (i-2,j+1) に置かれている
  • マス (i-2,j-1) に置かれている
  • マス (i-1,j-2) に置かれている
  • マス (i+1,j-2) に置かれている
  • マス (i+2,j-1) に置かれている

ただし、存在しないマスについての条件は常に満たされないものとします。

たとえば、マス (4,4) に置かれているコマは、以下の図で青く示されたマスに置かれているコマを取ることができます。

あなたがコマを置くことができるマスがいくつあるか求めてください。

制約

  • 1\leq N\leq10 ^ 9
  • 1\leq M\leq2\times10 ^ 5
  • 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

38

すでに置かれているコマは、以下の図で青く示されたマスに置かれたコマを取ることができます。

よって、あなたがすでに置かれているコマに取られないように自分のコマを置くことができるマスは残りの 38 マスです。

入力例 2

1000000000 1
1 1

出力例 2

999999999999999997

10 ^ {18} マスのうち、置くことができないマスはマス (1,1),(2,3),(3,2) の 3 マスのみです。

答えが 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

338

Score : 300 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 on square (i+2,j+1)
  • Placed on square (i+1,j+2)
  • Placed on square (i-1,j+2)
  • Placed on square (i-2,j+1)
  • Placed on square (i-2,j-1)
  • Placed on square (i-1,j-2)
  • Placed on square (i+1,j-2)
  • Placed on square (i+2,j-1)

Here, conditions involving non-existent squares are considered to never be satisfied.

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\leq2\times10^5
  • 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

38

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on the remaining 38 squares.

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999999999999997

Out of 10^{18} squares, only 3 squares cannot be used: squares (1,1), (2,3), and (3,2).

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

338