分数: 600 点
问题陈述
我们有一个网格 H 水平行和 W 垂直列。让广场 (i,j) 是位于 i第行和 j- 第列。
有 M 该网格上有障碍物。的 i第一个障碍物位于 Square (X_i, Y_i).
我们在 Square 上有一个车,即棋子 (1, 1)。一次移动,它可以无障碍地向右或向下移动任意数量的方格。
求车在两步或更少的时间内可以到达的方格数。
约束
- 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) 是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W M X_1 Y_1 \vdots X_M Y_M
输出
打印小车在两步或更少的时间内可以到达的方格数。
示例输入 1
4 3 2 2 2 3 3
示例输出 1
10
可以在两步或更短的时间内到达没有障碍物的每个方格。
示例输入 2
5 4 4 3 2 3 4 4 2 5 2
示例输出 2
14
每个没有障碍物的方格,除了 (4,4) 和 (5,4) 可以在两步或更短的时间内到达。
示例输入 3
200000 200000 0
示例输出 3
40000000000