C - 2x2 Placing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 行 N 列のマス目があります。 上から i 行目、左から j 列目のマスを (i,j) と表記します。 はじめ、マス目の上には何も置かれていません。

今から M 回の操作を行います。 i 回目 (1\leq i\leq M) の操作は以下の通りです。

  • マス (R_i,C_i) を左上とする 2 \times 2 の領域を占めるブロックを、既に置かれている他のブロックと位置が重ならない場合、またその場合に限り、マス目の上に置く。 より厳密には、マス集合 S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace に対し、既にマス目の上に置かれているブロックであって S に含まれるいずれかのマスを占めるものが存在するならば何も行わず、 存在しないならば S に含まれる 4 マス全体を占めるブロックを置く。

全ての操作を行った後、マス目の上に何個のブロックが置かれているか求めてください。

制約

  • 2\leq N \leq 10^9
  • 1\leq M \leq 2\times 10^5
  • 1\leq R_i,C_i \leq N-1
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
R_1 C_1
R_2 C_2
\vdots
R_M C_M

出力

答えを出力せよ。

入力例 1

4 3
1 1
2 2
2 3

出力例 1

2

以下の図は操作のようすを示したものであり、黒く塗られた領域がブロックを、赤枠で囲まれた領域が次にブロックを置きたい場所を表しています。

  • 1 回目の操作：マス (1,1) を左上とする 2 \times 2 の領域には何も置かれていないため、そこにブロックを置きます。
  • 2 回目の操作：マス (2,2) を左上とする 2 \times 2 の領域のうち、マス (2,2) 上に既に他のブロックが存在するため、何も行いません。
  • 3 回目の操作：マス (2,3) を左上とする 2 \times 2 の領域には何も置かれていないため、そこにブロックを置きます。

よって、全ての操作を行った後、マス目の上に 2 個のブロックが置かれています。

入力例 2

1000000000 4
1 1
1 101
101 1
101 101

出力例 2

4

全ての操作においてブロックを置くことができます。

入力例 3

8 10
6 5
7 3
6 7
3 4
4 2
3 7
1 3
7 4
6 1
6 1

出力例 3

8

(R_i,C_i)=(R_j,C_j) を満たす i,j\ (i\neq j) が存在することもあります。

Score : 300 points

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Initially, nothing is placed on the grid.

You will now perform M operations. The i-th operation (1\leq i\leq M) is as follows:

  • Place a block that occupies a 2 \times 2 region with cell (R_i,C_i) as the top-left corner on the grid if and only if its position does not overlap with any other blocks already placed. More precisely, for the set of cells S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace, if there exists a block already placed on the grid that occupies any cell in S, do nothing; otherwise, place a block that occupies all four cells in S.

After performing all operations, find how many blocks are placed on the grid.

Constraints

  • 2\leq N \leq 10^9
  • 1\leq M \leq 2\times 10^5
  • 1\leq R_i,C_i \leq N-1
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
R_1 C_1
R_2 C_2
\vdots
R_M C_M

Output

Print the answer.

Sample Input 1

4 3
1 1
2 2
2 3

Sample Output 1

2

The following diagram shows the operations, where black-filled regions represent blocks and red-framed regions represent where the next block is to be placed.

  • Operation 1: Nothing is placed in the 2 \times 2 region with cell (1,1) as the top-left corner, so place a block there.
  • Operation 2: Among the 2 \times 2 region with cell (2,2) as the top-left corner, there is already another block on cell (2,2), so do nothing.
  • Operation 3: Nothing is placed in the 2 \times 2 region with cell (2,3) as the top-left corner, so place a block there.

Thus, after performing all operations, two blocks are placed on the grid.

Sample Input 2

1000000000 4
1 1
1 101
101 1
101 101

Sample Output 2

4

Blocks can be placed in all operations.

Sample Input 3

8 10
6 5
7 3
6 7
3 4
4 2
3 7
1 3
7 4
6 1
6 1

Sample Output 3

8

There may exist i,j\ (i\neq j) such that (R_i,C_i)=(R_j,C_j).