/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 475 点
問題文
縦 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) は穴が空いていないマスである。
グリッド内に穴のない正方形は何個ありますか？
制約
- 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
穴のない正方形は全部で 6 個あります。
それらを列挙すると次の通りです。このうちはじめの 5 個は 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
Score : 475 points
Problem Statement
There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of the grid.
Each square of the grid is holed or not. There are exactly N holed squares: (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N).
When the triple of positive integers (i, j, n) satisfies the following condition, the square region whose top-left corner is (i, j) and whose bottom-right corner is (i + n - 1, j + n - 1) is called a holeless square.
- i + n - 1 \leq H.
- j + n - 1 \leq W.
- For every pair of non-negative integers (k, l) such that 0 \leq k \leq n - 1, 0 \leq l \leq n - 1, square (i + k, j + l) is not holed.
How many holeless squares are in the grid?
Constraints
- 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
- All (a_i, b_i) are pairwise different.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
H W N a_1 b_1 a_2 b_2 \vdots a_N b_N
Output
Print the number of holeless squares.
Sample Input 1
2 3 1 2 3
Sample Output 1
6
There are six holeless squares, listed below. For the first five, n = 1, and the top-left and bottom-right corners are the same square.
- The square region whose top-left and bottom-right corners are (1, 1).
- The square region whose top-left and bottom-right corners are (1, 2).
- The square region whose top-left and bottom-right corners are (1, 3).
- The square region whose top-left and bottom-right corners are (2, 1).
- The square region whose top-left and bottom-right corners are (2, 2).
- The square region whose top-left corner is (1, 1) and whose bottom-right corner is (2, 2).
Sample Input 2
3 2 6 1 1 1 2 2 1 2 2 3 1 3 2
Sample Output 2
0
There may be no holeless square.
Sample Input 3
1 1 0
Sample Output 3
1
The whole grid may be a holeless square.
Sample Input 4
3000 3000 0
Sample Output 4
9004500500