F - Grid Clipping Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

H 行 W 列のグリッドがあります。上から r 行目、左から c 列目のマスをマス (r,c) と呼びます。各マスは黒か白で塗られており、k=1,2,\ldots,N に対しマス (R_k,C_k) は黒で、それ以外の HW-N マスは白で塗られています。

このグリッドの中の縦 h 行、横 w 列の長方形領域であって、含まれるマスが全て白で塗られているようなものがいくつあるか求めてください。

より厳密には、以下の条件を全て満たす整数の組 (r_0, c_0) の個数を求めてください。

  • 1\le r_0 \le H-h+1
  • 1\le c_0 \le W-w+1
  • 0\le i< h,\ 0\le j< w を満たす全ての整数の組 (i,j) に対し、マス (r_0+i,c_0+j) は白で塗られている。

制約

  • 1\le h\le H\le 10^9
  • 1\le w\le W\le 10^9
  • 0\le N\le 2\times 10^5
  • 1\le R_k\le H
  • 1\le C_k\le W
  • (R_{k_1},C_{k_1}) \neq (R_{k_2},C_{k_2}) (k_1 \neq k_2)
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

H W h w N
R_1 C_1
R_2 C_2
\vdots
R_N C_N

出力

答えを出力せよ。

入力例 1

3 4 2 2 3
1 3
2 4
3 1

出力例 1

2

下図の赤で囲まれた 2 つの長方形領域が条件を全て満たします。

入力例 2

4 4 3 2 2
2 2
3 4

出力例 2

0

条件を全て満たす長方形領域は存在しません。

入力例 3

449 449 3 14 0

出力例 3

194892

入力例 4

31 9 5 7 10
14 8
8 4
18 8
12 1
8 5
9 6
18 1
14 7
5 6
26 7

出力例 4

12

Score : 500 points

Problem Statement

There is a grid with H rows and W columns. The cell at the r-th row from the top and c-th column from the left is called cell (r,c). Each cell is painted black or white: cell (R_k,C_k) is black for k=1,2,\ldots,N, and the remaining HW-N cells are white.

Find the number of rectangular regions in this grid with h rows and w columns such that all cells contained in them are painted white.

More formally, find the number of pairs of integers (r_0, c_0) satisfying all of the following conditions:

  • 1\le r_0 \le H-h+1
  • 1\le c_0 \le W-w+1
  • Cell (r_0+i,c_0+j) is painted white for all pairs of integers (i,j) satisfying 0\le i< h,\ 0\le j< w.

Constraints

  • 1\le h\le H\le 10^9
  • 1\le w\le W\le 10^9
  • 0\le N\le 2\times 10^5
  • 1\le R_k\le H
  • 1\le C_k\le W
  • (R_{k_1},C_{k_1}) \neq (R_{k_2},C_{k_2}) (k_1 \neq k_2)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

H W h w N
R_1 C_1
R_2 C_2
\vdots
R_N C_N

Output

Output the answer.

Sample Input 1

3 4 2 2 3
1 3
2 4
3 1

Sample Output 1

2

The two rectangular regions enclosed in red in the figure below satisfy all the conditions.

Sample Input 2

4 4 3 2 2
2 2
3 4

Sample Output 2

0

No rectangular region satisfies all the conditions.

Sample Input 3

449 449 3 14 0

Sample Output 3

194892

Sample Input 4

31 9 5 7 10
14 8
8 4
18 8
12 1
8 5
9 6
18 1
14 7
5 6
26 7

Sample Output 4

12