AT_abc186_f [ABC186F] Rook on Grid

题目描述

有一个高为 $H$，宽为 $W$ 的网格。第 $i$ 行第 $j$ 列的格子记作格子 $(i,j)$。

在网格上有 $M$ 个障碍物，第 $i$ 个障碍物位于格子 $(X_i, Y_i)$。

在格子 $(1,1)$ 上放有一枚“飞车”棋子。飞车棋子可以从当前位置沿着右方或下方的直线移动，每次移动可以到达不越过障碍物的格子，且每次移动算作一步。

请你求出，飞车棋子在 $2$ 步以内能够到达的格子的数量。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$ $M$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$

输出格式

输出飞车棋子在 $2$ 步以内能够到达的格子的数量。

输入输出样例 #1

输入 #1

4 3 2
2 2
3 3

输出 #1

10

输入输出样例 #2

输入 #2

5 4 4
3 2
3 4
4 2
5 2

输出 #2

14

输入输出样例 #3

输入 #3

200000 200000 0

输出 #3

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)$ 互不相同
• 所有输入均为整数

样例解释 1

没有障碍物时，所有没有障碍物的格子都可以在 $2$ 步以内到达。

样例解释 2

在没有障碍物的格子中，除了 $(4,4)$ 和 $(5,4)$ 以外，所有格子都可以在 $2$ 步以内到达。

由 ChatGPT 4.1 翻译