E - Packing Under Range Regulations

Contest Duration: 2021-08-14(Sat) 12:00 - 2021-08-14(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Packing Under Range Regulations Editorial

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$T$ 個のテストケースについて、以下の問題を解いてください。

$1,2,\dots,10^9$ の番号がついた $10^9$ 個の箱と、 $1,2,\dots,N$ の番号がついた $N$ 個のボールがあります。
それぞれの箱に入れることのできるボールの個数は多くとも $1$ 個です。
以下の条件を満たすように、 $N$ 個のボールを全て箱に入れることができるか判定してください。

全ての $1$ 以上 $N$ 以下の整数 $i$ について、番号 $i$ のボールが $L_i$ 以上 $R_i$ 以下の番号がついた箱に入っている。

制約

$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$
$1$ つの入力に含まれるテストケースについて、それらの $N$ の総和は $2 \times 10^5$ を超えない。

入力

入力は標準入力から与えられる。入力の $1$ 行目は以下の形式である。

$T$

その後、 $T$ 個のテストケースが続く。各テストケースは以下の形式で与えられる。

 $N$ 
 $L_1$   $R_1$ 
 $L_2$   $R_2$ 
 $\dots$ 
 $L_N$   $R_N$

出力

出力は $T$ 行からなる。
$i(1 \le i \le T)$ 行目には、 $i$ 番目に入力されたテストケースについて、問題文中の条件を満たすように $N$ 個のボールを全て箱に入れることができるなら Yes 、そうでないなら No と出力せよ。
なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。

入力例 1Copy

Copy

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

出力例 1Copy

Copy

Yes
No

この入力には $2$ つのテストケースが含まれます。

$1$ つ目のテストケースについて、以下のようにボールを箱に入れると、問題文中の条件を満たすように $3$ 個のボールを全て箱に入れることができるので、 Yes と出力します。
- ボール $1$ を箱 $1$ に入れる。
- ボール $2$ を箱 $2$ に入れる。
- ボール $3$ を箱 $3$ に入れる。
$2$ つ目のテストケースについて、問題文中の条件を満たすように $5$ 個のボールを全て箱に入れることはできないので、 No と出力します。

Score : $500$ points

Problem Statement

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).

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$ .

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$

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 printNo otherwise.
The checker is case-insensitive; it will accept both uppercase and lowercase letters.

Sample Input 1Copy

Copy

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

Sample Output 1Copy

Copy

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.