9470: ABC214 —— E - Packing Under Range Regulations
[Creator : ]
Description
Solve the following problem for $T$ test cases.
There are $10^9$ boxes numbered $1,2,\dots,10^9$ and $N$ balls numbered $1,2,\dots,N$.
Each box can contain at most one ball.
Determine whether it is possible to put all $N$ balls in the boxes so that the following condition will be satisfied.
- For each integer $i$ from $1$ through $N$, the ball numbered $i$ is in a box numbered between $L_i$ and $R_i$ (inclusive).
There are $10^9$ boxes numbered $1,2,\dots,10^9$ and $N$ balls numbered $1,2,\dots,N$.
Each box can contain at most one ball.
Determine whether it is possible to put all $N$ balls in the boxes so that the following condition will be satisfied.
- For each integer $i$ from $1$ through $N$, the ball numbered $i$ is in a box numbered between $L_i$ and $R_i$ (inclusive).
Input
Input is given from Standard Input. The first line is in the following format:
```
$T$
```
Then, $T$ test cases follows, each of which is in the following format:
```
$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\dots$
$L_N$ $R_N$
```
```
$T$
```
Then, $T$ test cases follows, each of which is in the following format:
```
$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\dots$
$L_N$ $R_N$
```
Output
Your output should have $T$ lines.
In the $i$-th $(1 \le i \le T)$ line, print `Yes` if it is possible to put all $N$ balls in the boxes so that the condition will be satisfied in the $i$-th test case in the input, and print`No` otherwise.
The checker is case-insensitive; it will accept both uppercase and lowercase letters.
In the $i$-th $(1 \le i \le T)$ line, print `Yes` if it is possible to put all $N$ balls in the boxes so that the condition will be satisfied in the $i$-th test case in the input, and print`No` otherwise.
The checker is case-insensitive; it will accept both uppercase and lowercase letters.
Constraints
- $1 \le T \le 2 \times 10^5$
- $1 \le N \le 2 \times 10^5$
- $1 \le L_i \le R_i \le 10^9$
- The sum of $N$ across the test cases in one input is at most $2 \times 10^5$.
- $1 \le N \le 2 \times 10^5$
- $1 \le L_i \le R_i \le 10^9$
- The sum of $N$ across the test cases in one input is at most $2 \times 10^5$.
Sample 1 Input
2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000
Sample 1 Output
Yes
No
This input contains two test cases.
-
In the 1-st test case, the following way to put the three balls would satisfy the condition, so we should print Yes.
- Put Ball 1 in Box 1.
- Put Ball 2 in Box 2.
- Put Ball 3 in Box 3.
-
In the 2-nd test case, there is no way to put the five balls to satisfy the condition, so we should print No.