Defect-free Squares

题目描述

有一个 $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$。 对于所有满足 $0 \leq k \leq n - 1, 0 \leq l \leq n - 1$ 的非负整数对 $(k, l)$，方格 $(i + k, j + l)$ 都不是有洞的。

问格子中有多少个无洞的正方形？

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $N$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_N$ $b_N$

输出格式

输出无洞正方形的个数。

2 3 1
2 3

6

3 2 6
1 1
1 2
2 1
2 2
3 1
3 2

0

1 1 0

1

3000 3000 0

9004500500

提示

$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)$ 两两不同。 所有输入值都是整数。共有六个无洞的正方形，列举如下。前五个的 $n = 1$，左上角与右下角是同一个方格。

左上角与右下角均为 $(1, 1)$ 的方形区域。 左上角与右下角均为 $(1, 2)$ 的方形区域。 左上角与右下角均为 $(1, 3)$ 的方形区域。 左上角与右下角均为 $(2, 1)$ 的方形区域。 左上角与右下角均为 $(2, 2)$ 的方形区域。 左上角为 $(1, 1)$、右下角为 $(2, 2)$ 的方形区域。
也可能没有无洞的正方形。
整个网格也可能是一个无洞的正方形。

标签: AtCoder|abc311E

来源

AtCoder|abc311E