Reclamation

题意翻译

### 题意简述 给定一个大小为 $r*c$ 的二维环形网格图，每一行的第 $1$ 格和第 $c$ 格同样相邻。 现在按照给定的顺序将 $n$ 个格子变成障碍物。一个格子可以变成障碍的条件为该格子变成障碍后仍然存在一条从第 $1$ 行到第 $r$ 行的路径。如果一个格子不可以变成障碍，就跳过该操作并且继续处理接下来的格子。路径为四相邻规则。 您需要求出最多可以有多少个格子变成障碍物。 ### 输入格式 第一行是三个整数 $r,c,n (1<=r,c<=3000,1<=n<=3 \cdot 10^5)$。 接下来n行，每行两个正整数 $r_i , c_i$ ，表示将位于$r_i $行, $c_i$列的格子变成障碍物。 ### 输出格式 输出一个整数表示答案。

题目描述

In a far away land, there exists a planet shaped like a cylinder. There are three regions in this planet: top, bottom, and side as shown in the following picture. Both the top and the bottom areas consist of big cities. The side area consists entirely of the sea. One day, a city decides that it has too little space and would like to reclamate some of the side area into land. The side area can be represented by a grid with $ r $ rows and $ c $ columns — each cell represents a rectangular area in the side area. The rows are numbered 1 through $ r $ from top to bottom, while the columns are numbered 1 through $ c $ from left to right. Two cells are adjacent if they share a side. In addition, two cells located on the same row — one in the leftmost column, and the other in the rightmost column — are also adjacent. Initially, all of the cells are occupied by the sea. The plan is to turn some of those cells into land one by one in a particular order that will be given to you. However, the sea on the side area is also used as a major trade route. More formally, it is not allowed to reclamate the sea cells into land in such way that there does not exist a sequence of cells with the following property: - All cells in the sequence are occupied by the sea (i.e., they are not reclamated). - The first cell in the sequence is in the top row. - The last cell in the sequence is in the bottom row. - Consecutive cells in the sequence are adjacent. Thus, the plan is revised. Each time a cell is going to be turned from sea to land, the city first needs to check whether or not it would violate the above condition by doing that. If it would, then the cell is not turned into land and the plan proceeds into the next cell. Otherwise, the cell is turned into land. Your job is to simulate this and output the number of cells that were successfully turned into land.

输入输出格式

输入格式

The first line consists of three integers $ r $ , $ c $ , and $ n $ ( $ 1<=r,c<=3000 $ , $ 1<=n<=3·10^{5} $ ). Then, $ n $ lines follow, describing the cells in the order you will reclamate them. Each line will consists of two integers: $ r_{i} $ and $ c_{i} $ ( $ 1<=r_{i}<=r $ , $ 1<=c_{i}<=c $ ), which represents the cell located at row $ r_{i} $ and column $ c_{i} $ . All of the lines describing the cells will be distinct.

输出格式

You should output a single number representing the number of cells that were successfully turned to land.

输入输出样例

输入样例 #1

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

输出样例 #1

6

说明

The pictures below show the sequence of reclamations that are performed in the example input. Blue cells represent the cells occupied by sea, while other colored cells represent land. The latest cell that are reclamated is colored either yellow or red, depending on whether the addition violates the condition in the statement. The dashed red line represents a possible trade route, if it exists.       No route exists, so this reclamation is not performed.   No route exists, skipped.  Remember that the leftmost and rightmost cells in the same row are adjacent.  No route exists, skipped. Hence the result is:  There are 6 successful reclamation and 3 failed ones.