← 返回题目列表

AtCoder · abc304_d

G. 小菜一碟

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

分数: 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

每块上面都有一个草莓。