分数: 475 点
问题陈述
有一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部算起的第行和 j- 网格左侧的第列。
网格的每个方格是否有孔。正好有 N 有孔方块: (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N).
当三重正整数 (i, j, n) 满足以下条件,左上角为的正方形区域 (i, j) 其右下角是 (i + n - 1, j + n - 1) 被称为 无孔方形.
- i + n - 1 \leq H.
- j + n - 1 \leq W.
- 对于每对非负整数 (k, l) 这样 0 \leq k \leq n - 1, 0 \leq l \leq n - 1,方形 (i + k, j + l) 没有打孔。
网格中有多少个无孔方块?
约束
- 1 \leq H, W \leq 3000
- 0 \leq N \leq \min(H \times W, 10^5)
- 1 \leq a_i \leq H
- 1 \leq b_i \leq W
- 全部 (a_i, b_i) 两两不同。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
H W N a_1 b_1 a_2 b_2 \vdots a_N b_N
输出
打印无孔方块的数量。
示例输入 1
2 3 1 2 3
示例输出 1
6
有六个无孔方块,如下所列。对于前五个, n = 1,并且左上角和右下角是同一个正方形。
- 左上角和右下角为的正方形区域 (1, 1).
- 左上角和右下角为的正方形区域 (1, 2).
- 左上角和右下角为的正方形区域 (1, 3).
- 左上角和右下角为的正方形区域 (2, 1).
- 左上角和右下角为的正方形区域 (2, 2).
- 左上角为的正方形区域 (1, 1) 其右下角是 (2, 2).
示例输入 2
3 2 6 1 1 1 2 2 1 2 2 3 1 3 2
示例输出 2
0
可能没有无孔正方形。
示例输入 3
1 1 0
示例输出 3
1
整个网格可能是一个无孔的正方形。
示例输入 4
3000 3000 0
示例输出 4
9004500500