A Piece of Cake

题目描述

有一个带有若干草莓的矩形蛋糕位于 $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$。没有两个草莓具有相同的坐标。 Takahashi 将用刀按如下方式把蛋糕切成若干块。

首先，沿平行于 $y$ 轴的 $A$ 条不同直线切割蛋糕：直线 $x = a_1$、$x = a_2$、…、$x = a_A$。 接着，沿平行于 $x$ 轴的 $B$ 条不同直线切割蛋糕：直线 $y = b_1$、$y = b_2$、…、$y = b_B$。

结果，蛋糕将被分成 $(A+1)(B+1)$ 个矩形小块。Takahashi 将只选择其中一块来吃。输出所选小块上草莓数量的最小可能值和最大可能值。 在此保证最终小块的边界上没有草莓。更形式化的说明请参阅下面的约束条件。

输入格式

输入从标准输入按如下格式给出： $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$

7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4

0 2

4 4
4
1 1
3 1
3 3
1 3
1
2
1
2

1 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$ 所有输入值均为整数。总共有九块：六块没有草莓，一块有一个草莓，两个有两个草莓。因此，当只选择其中一块来吃时，所选小块上草莓数量的最小可能值为 $0$，最大可能值为 $2$。
每一块上都有一个草莓。

标签: AtCoder|abc304D

来源

AtCoder|abc304D