AT_abc311_e [ABC311E] Defect-free Squares

[problemUrl]: https://atcoder.jp/contests/abc311/tasks/abc311_e 縦 $ H $ 行, 横 $ W $ 列のグリッドがあります。グリッドの上から $ i $ 行目, 左から $ j $ 列目のマスを $ (i,\ j) $ と呼びます。 グリッドの各マスは穴の空いたマスとそうでないマスのどちらかです。穴が空いたマスは $ (a_1,\ b_1),\ (a_2,\ b_2),\ \dots,\ (a_N,\ b_N) $ のちょうど $ 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 $

穴のない正方形の個数を出力せよ。

### 制約 - $ 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) $ は互いに異なる - 入力される値は全て整数 ### Sample Explanation 1 穴のない正方形は全部で $ 6 $ 個あります。 それらを列挙すると次の通りです。このうちはじめの $ 5 $ 個は $ n\ =\ 1 $ の場合であり、領域の左上隅のマスと右下隅のマスが一致します。 - $ (1,\ 1) $ を左上隅かつ右下隅とする正方形領域 - $ (1,\ 2) $ を左上隅かつ右下隅とする正方形領域 - $ (1,\ 3) $ を左上隅かつ右下隅とする正方形領域 - $ (2,\ 1) $ を左上隅かつ右下隅とする正方形領域 - $ (2,\ 2) $ を左上隅かつ右下隅とする正方形領域 - $ (1,\ 1) $ を左上隅, $ (2,\ 2) $ を右下隅とする正方形領域 ### Sample Explanation 2 穴のない正方形が存在しない場合もあります。 ### Sample Explanation 3 穴のない正方形がグリッド全体と一致する場合もあります。