102454: [AtCoder]ABC245 E - Wrapping Chocolate
Description
Score : $500$ points
Problem Statement
Takahashi has $N$ pieces of chocolate. The $i$-th piece has a rectangular shape with a width of $A_i$ centimeters and a length of $B_i$ centimeters.
He also has $M$ boxes. The $i$-th box has a rectangular shape with a width of $C_i$ centimeters and a length of $D_i$ centimeters.
Determine whether it is possible to put the $N$ pieces of chocolate in the boxes under the conditions below.
- A box can contain at most one piece of chocolate.
- $A_i \leq C_j$ and $B_i \leq D_j$ must hold when putting the $i$-th piece of chocolate in the $j$-th box (they cannot be rotated).
Constraints
- $1 \leq N \leq M \leq 2\times 10^5$
- $1 \leq A_i,B_i,C_i,D_i \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $A_1$ $\ldots$ $A_N$ $B_1$ $\ldots$ $B_N$ $C_1$ $\ldots$ $C_M$ $D_1$ $\ldots$ $D_M$
Output
If it is possible to put the $N$ pieces of chocolate in the boxes, print Yes; otherwise, print No.
Sample Input 1
2 3 2 4 3 2 8 1 5 2 10 5
Sample Output 1
Yes
We can put the first piece of chocolate in the third box and the second piece in the first box.
Sample Input 2
2 2 1 1 2 2 100 1 100 1
Sample Output 2
No
A box can contain at most one piece of chocolate.
Sample Input 3
1 1 10 100 100 10
Sample Output 3
No
Sample Input 4
1 1 10 100 10 100
Sample Output 4
Yes
Input
题意翻译
### 题目描述 高桥先生有 $N$ 块巧克力。第 $i$ 块巧克力是长为 $A_i$，宽为 $B_i$ cm 的长方形。高桥先生还有 $M$ 个盒子。第 $i$ 个盒子是长为 $C_i$，宽为 $D_i$ cm 的长方形。 请问是否能在满足以下条件的情况下把所有巧克力放入盒子中。 - 一个盒子中最多放入一块巧克力。 - 当把第 $i$ 块巧克力放入第 $j$ 个盒子的时候，必须满足 $A_i\le C_j$ 并且 $B_i\le D_j$（不允许旋转）。 ### 输入格式 从标准格式读入数据，格式如下： > $N\space M\space A_i … A_N\space B_i … B_N\space C_i … C_N\space D_i … D_N$ ### 输出格式 如果可以把所有巧克力都放在盒子里，就输出 ``Yes``，否则输出 ``No``。 ### 样例解释 1 把第 $1$ 块巧克力放进第 $3$ 个盒子，把第 $2$ 块巧克力放进第 $1$ 个盒子。 ### 样例解释 2 如果想全部放入盒子中，第 $1$ 个盒子至少应该放 $2$ 块巧克力。 ### 说明/提示 - $1\le N\le M\le 2\times 10^5$ - $1\le A_i,B_i,C_i,D_i\le 10^9$ - 所有数据均为整数。 —— Translated by 2c_sOutput
问题描述
高桥有$N$块巧克力。第$i$块巧克力有$A_i$厘米宽，$B_i$厘米长的矩形形状。
他还$M$个盒子。第$i$个盒子有$C_i$厘米宽，$D_i$厘米长的矩形形状。
确定是否可以在以下条件下将$N$块巧克力放入盒子中。
- 一个盒子最多可以装一块巧克力。
- 将第$i$块巧克力放入第$j$个盒子时，必须满足$A_i \leq C_j$和$B_i \leq D_j$（它们不能旋转）。
约束条件
- $1 \leq N \leq M \leq 2\times 10^5$
- $1 \leq A_i,B_i,C_i,D_i \leq 10^9$
- 输入中的所有值都是整数。
输入
输入从标准输入按以下格式给出：
$N$ $M$ $A_1$ $\ldots$ $A_N$ $B_1$ $\ldots$ $B_N$ $C_1$ $\ldots$ $C_M$ $D_1$ $\ldots$ $D_M$
输出
如果可以将$N$块巧克力放入盒子中，请打印Yes；否则，打印No。
样例输入1
2 3 2 4 3 2 8 1 5 2 10 5
样例输出1
Yes
我们可以将第一块巧克力放入第三个盒子，将第二块巧克力放入第一个盒子。
样例输入2
2 2 1 1 2 2 100 1 100 1
样例输出2
No
一个盒子最多可以装一块巧克力。
样例输入3
1 1 10 100 100 10
样例输出3
No
样例输入4
1 1 10 100 10 100
样例输出4
Yes