← 返回题目列表

Codeforces · 325/D

D. 回收

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

在遥远的土地上,存在着一颗圆柱体的行星。这个星球分为三个区域:顶部、底部和侧面,如下图所示。

顶部和底部区域均由大城市组成。侧面区域完全由大海组成。

有一天,一座城市认为它的空间太小,想要将一些侧面区域开垦为土地。侧面区域可以用 r 行和 c 列的网格表示 - 每个单元格代表侧面区域中的一个矩形区域。行从上到下编号为 1 到 r,列从左到右编号为 1 到 c。如果两个单元共用一条边,则它们是相邻的。此外,位于同一行的两个单元格(一个位于最左列,另一个位于最右列)也是相邻的。

最初,所有单元格都被大海占据。计划是按照给你的特定顺序将其中一些单元格一一变成土地。

然而,侧面区域的海域也被用作主要的贸易路线。更正式地说,不允许以不存在具有以下属性的单元序列的方式将海洋单元填海成陆地:

- 序列中的所有单元格都被海洋占据(即,它们未被开垦)。
- 序列中的第一个单元格位于顶行。
- 序列中的最后一个单元格位于底行。
- 序列中的连续单元格是相邻的。

因此,该计划被修改。每次将一个单元从海上转向陆地时,城市首先需要检查这样做是否会违反上述条件。如果是的话,那么该单元就不会变成土地,并且计划将继续进行下一个单元。否则,细胞就会变成土地。

你的工作是模拟这个并输出成功变成土地的单元格数量。

输入

第一行由三个整数 r、c 和 n (1 ≤ r, c ≤ 3000, 1 ≤ n ≤ 3·105) 组成。然后,接下来是 n 行,按照您将回收的顺序描述单元格。每行由两个整数组成:ri 和 ci (1 ≤ ri ≤ r, 1 ≤ ci ≤ c),表示位于 ri 行和 ci 列的单元格。所有描述细胞的线条都是不同的。

输出

您应该输出一个数字,表示成功转向着陆的单元格数量。

示例

输入 #1

3 4 9
2 2
3 2
2 3
3 4
3 1
1 3
2 1
1 1
1 4

输出 #1

6

注意

下图显示了示例输入中执行的回收序列。蓝色单元格代表海洋占据的单元格,而其他颜色单元格代表陆地。最新回收的单元格颜色为黄色或红色,具体取决于添加是否违反语句中的条件。红色虚线代表一条可能的贸易路线(如果存在)。

不存在路由,因此不执行此回收。

不存在路线,已跳过。

请记住,同一行中最左边和最右边的单元格是相邻的。

不存在路线,已跳过。

因此结果是:

回收成功6次,失败3次。