← 返回题目列表

AtCoder · abc186_f

F. 车在网格上

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

分数: 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