← 返回题目列表

AtCoder · abc311_e

H. 无缺陷方块

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

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