← 返回题目列表

AtCoder · abc436_c

C. 2x2 放置

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

分数: 300 点

问题陈述

有一个网格 N 行和 N 列。 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。 最初,网格上没有放置任何内容。

您现在将执行 M 操作。的 i第次操作 (1\leq i\leq M) 如下:

  • 放置一个占据 2 \times 2 包含单元格的区域 当且仅当其位置不与已放置的任何其他块重叠时, (R_i,C_i) 作为网格的左上角。 更准确地说,对于一组单元格 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.

执行完所有操作后,找出网格上放置了多少块。

约束

  • 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: 中没有放置任何内容 2 \times 2 包含单元格的区域 当且仅当其位置不与已放置的任何其他块重叠时, (1,1) 作为左上角,所以在那里放置一个块。
  • 操作 2:其中 2 \times 2 包含单元格的区域 当且仅当其位置不与已放置的任何其他块重叠时, (2,2) 作为左上角,单元格上已经有另一个块 (2,2),所以什么也不做。
  • 操作 3: 中没有放置任何内容 2 \times 2 包含单元格的区域 当且仅当其位置不与已放置的任何其他块重叠时, (2,3) 作为左上角,所以在那里放置一个块。

因此,在执行所有操作之后,两个块被放置在网格上。


示例输入 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

可能存在 i,j\ (i\neq j) 这样 (R_i,C_i)=(R_j,C_j).