/ 
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 と出力せよ。
なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。
入力例 1
2 3 1 2 2 3 3 3 5 1 2 2 3 3 3 1 3 999999999 1000000000
出力例 1
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 1
2 3 1 2 2 3 3 3 5 1 2 2 3 3 3 1 3 999999999 1000000000
Sample Output 1
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.