分数: 400 点
问题陈述
有一个长方形的蛋糕,上面有一些草莓 xy- 平面。蛋糕占据矩形面积 \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace.
有 N 蛋糕上的草莓,以及 i第草莓是 (p_i, q_i) 为 i = 1, 2, \ldots, N。没有两个草莓具有相同的坐标。
高桥将用刀将蛋糕切成几块,如下。
- 首先,将蛋糕沿着 A 不同的线平行于 y-轴:线 x = a_1, x = a_2, \ldots, x = a_A.
- 接下来,沿着切蛋糕 B 不同的线平行于 x-轴:线 y = b_1, y = b_2, \ldots, y = b_B.
这样一来,蛋糕就会被分成 (A+1)(B+1) 矩形块。高桥只会选择其中的一块来吃。在所选碎片上打印出草莓的最小和最大数量。
这里,保证最终碎片的边缘没有草莓。有关更正式的描述,请参阅下面的约束。
约束
- 3 \leq W, H \leq 10^9
- 1 \leq N \leq 2 \times 10^5
- 0 \lt p_i \lt W
- 0 \lt q_i \lt H
- i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
- 1 \leq A, B \leq 2 \times 10^5
- 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
- 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
- p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
- q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
W H N p_1 q_1 p_2 q_2 \vdots p_N q_N A a_1 a_2 \ldots a_A B b_1 b_2 \ldots b_B
输出
打印尽可能少的草莓数量 m 和最大可能数量 M 位于所选片段上,格式如下,以空格分隔。
m M
示例输入 1
7 6 5 6 1 3 1 4 2 1 5 6 2 2 2 5 2 3 4
示例输出 1
0 2
共有九块:六块有零个草莓,一块有一个草莓,两块有两个草莓。因此,当只选择其中一块吃时,所选择的一块上的草莓的最小可能数量是 0,最大可能数量为 2.
示例输入 2
4 4 4 1 1 3 1 3 3 1 3 1 2 1 2
示例输出 2
1 1
每块上面都有一个草莓。