← 返回题目列表

AtCoder · abc466_d

D. 放置车

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

分数: 400 点

问题陈述

有一个网格 N 行和 N 列。

最初,网格上没有放置任何内容。
从这个状态开始,高桥表演 M 网格上的操作按顺序进行。的 i第次操作 (1\leq i\leq M) 如下。

  • 移除放置在单元格上的所有碎片 R_i从顶部算起的第 3 行。
  • 接下来,移除放置在单元格上的所有碎片 C_i左起第 列。
  • 最后,在单元格上放置一块 R_i从顶部开始的第行和 C_i左起第 列。

输出放置在网格上的棋子数量 M 操作。

约束

  • 1 \leq N \leq 3\times 10^5
  • 1 \leq M \leq 3\times 10^5
  • 1 \leq R_i \leq N
  • 1 \leq C_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
R_1 C_1
R_2 C_2
\vdots
R_M C_M

输出

输出放置在网格上的棋子数量 M 操作。


示例输入 1

3 6
1 1
1 2
3 3
3 2
1 3
1 3

示例输出 1

2

最初,在三行三列的网格上没有放置任何东西,并且通过每次操作如下移除和放置棋子。
下面,位于 i从顶部开始的第行和 j从左边算起的第列表示为单元格 (i,j).

  • 在第一个操作中,将一块放置在单元格上 (1,1).
  • 在第二次操作中,该部件被从单元格中移除 (1,1),并将一块放置在单元格上 (1,2).
  • 在第三次操作中,将一块放置在单元格上 (3,3).
  • 在第四次操作中,碎片被从单元中移除 (1,2) 和细胞 (3,3),并将一块放置在单元格上 (3,2).
  • 在第五次操作中,将一块放置在单元格上 (1,3).
  • 在第六次操作中,该零件从单元中移除 再次 (1,3),并将一块放置在单元格上 (1,3) 。

最终状态下,单元格上各有一个 (1,3) 和细胞 (3,2),所以输出 2.


示例输入 2

2 3
1 2
2 1
1 1

示例输出 2

1