← 返回题目列表

AtCoder · abc449_f

F. 网格裁剪

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

分数: 500 点

问题陈述

有一个网格 H 行和 W 列。牢房位于 r从顶部算起的第行和 c从左边算起的第列称为单元格 (r,c)。每个单元格被漆成黑色或白色:单元格 (R_k,C_k) 为黑色 k=1,2,\ldots,N,剩余的 HW-N 细胞为白色。

找到该网格中矩形区域的数量 h 行和 w 列,其中包含的所有单元格都涂成白色。

更正式地说,找到整数对的数量 (r_0, c_0) 满足以下所有条件:

  • 1\le r_0 \le H-h+1
  • 1\le c_0 \le W-w+1
  • 细胞 所有整数对的 (r_0+i,c_0+j) 被涂成白色 (i,j) 满意 0\le i< h,\ 0\le j< w.

约束

  • 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

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