Rook on Grid

题目描述

我们有一个 $H$ 行 $W$ 列的网格。设方格 $(i,j)$ 为第 $i$ 行第 $j$ 列的方格。 网格上有 $M$ 个障碍物。第 $i$ 个障碍物位于方格 $(X_i, Y_i)$。 我们有一个车（象棋棋子），位于方格 $(1, 1)$。在一次移动中，它可以向右或向下移动，经过任意多个没有障碍物的方格。 求车在最多两次移动内可以到达的方格数量。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $M$ $X_1$ $Y_1$ $\vdots$ $X_M$ $Y_M$

输出格式

输出车在最多两次移动内可以到达的方格数量。

4 3 2
2 2
3 3

10

5 4 4
3 2
3 4
4 2
5 2

14

200000 200000 0

40000000000

提示

$1\leq H,W \leq 2\times 10^5$ $0\leq M \leq 2\times 10^5$ $1\leq X_i \leq H$ $1\leq Y_i \leq W$ $(X_i,Y_i) \neq (1,1)$ $(X_i,Y_i)$ 是互不相同的。 输入中的所有数值均为整数。每个没有障碍物的方格都可以在最多两次移动内到达。
除了 $(4,4)$ 和 $(5,4)$ 之外，每个没有障碍物的方格都可以在最多两次移动内到达。

标签: AtCoder|abc186F

来源

AtCoder|abc186F