309952: CF1764E. Doremy's Number Line
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Doremy's Number Line
题意翻译
给定两个长 $n$ 的序列 $a,b$，和一个整数 $k$，还有一个没有整数着色的数轴。 你需要找到一个长 $n$ 的排列 $p$，然后执行 $n$ 次操作。 对于第 $i$ 次操作，你需要找到一个整数 $x$ 满足 $x\le a_{p_i}$ 或者存在一个已经涂色的正数 $y$ 使得 $y\le a_{p_i}$ 且 $x\le y+b_{p_i}$，然后将 $x$ 涂上颜色 $p_i$。 判断 $k$ 是否能被涂上颜色 $1$。题目描述
Doremy has two arrays $ a $ and $ b $ of $ n $ integers each, and an integer $ k $ . Initially, she has a number line where no integers are colored. She chooses a permutation $ p $ of $ [1,2,\ldots,n] $ then performs $ n $ moves. On the $ i $ -th move she does the following: - Pick an uncolored integer $ x $ on the number line such that either: - $ x \leq a_{p_i} $ ; or - there exists a colored integer $ y $ such that $ y \leq a_{p_i} $ and $ x \leq y+b_{p_i} $ . - Color integer $ x $ with color $ p_i $ . Determine if the integer $ k $ can be colored with color $ 1 $ .输入输出格式
输入格式
The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 10^5 $ , $ 1 \le k \le 10^9 $ ). Each of the following $ n $ lines contains two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i,b_i \le 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式
For each test case, output "YES" (without quotes) if the point $ k $ can be colored with color $ 1 $ . Otherwise, output "NO" (without quotes). You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).
输入输出样例
输入样例 #1
6
4 16
5 3
8 12
10 7
15 1
4 16
8 12
10 7
15 1
5 3
4 16
10 7
15 1
5 3
8 12
4 16
15 1
5 3
8 12
10 7
1 1000000000
500000000 500000000
2 1000000000
1 999999999
1 1输出样例 #1
NO
YES
YES
YES
NO
YES说明
For the first test case, it is impossible to color point $ 16 $ with color $ 1 $ . For the second test case, $ p=[2,1,3,4] $ is one possible choice, the detail is shown below. - On the first move, pick $ x=8 $ and color it with color $ 2 $ since $ x=8 $ is uncolored and $ x \le a_2 $ . - On the second move, pick $ x=16 $ and color it with color $ 1 $ since there exists a colored point $ y=8 $ such that $ y\le a_1 $ and $ x \le y + b_1 $ . - On the third move, pick $ x=0 $ and color it with color $ 3 $ since $ x=0 $ is uncolored and $ x \le a_3 $ . - On the forth move, pick $ x=-2 $ and color it with color $ 4 $ since $ x=-2 $ is uncolored and $ x \le a_4 $ . - In the end, point $ -2,0,8,16 $ are colored with color $ 4,3,2,1 $ , respectively. For the third test case, $ p=[2,1,4,3] $ is one possible choice. For the fourth test case, $ p=[2,3,4,1] $ is one possible choice.Input
题意翻译
给定两个长 $n$ 的序列 $a,b$，和一个整数 $k$，还有一个没有整数着色的数轴。 你需要找到一个长 $n$ 的排列 $p$，然后执行 $n$ 次操作。 对于第 $i$ 次操作，你需要找到一个整数 $x$ 满足 $x\le a_{p_i}$ 或者存在一个已经涂色的正数 $y$ 使得 $y\le a_{p_i}$ 且 $x\le y+b_{p_i}$，然后将 $x$ 涂上颜色 $p_i$。 判断 $k$ 是否能被涂上颜色 $1$。Output
**题意翻译**
给定两个长度为 $ n $ 的序列 $ a, b $，和一个整数 $ k $，还有一个没有整数着色的数轴。
你需要找到一个长度为 $ n $ 的排列 $ p $，然后执行 $ n $ 次操作。
对于第 $ i $ 次操作，你需要找到一个整数 $ x $ 满足 $ x \leq a_{p_i} $ 或者存在一个已经涂色的正数 $ y $ 使得 $ y \leq a_{p_i} $ 且 $ x \leq y + b_{p_i} $，然后将 $ x $ 涂上颜色 $ p_i $。
判断 $ k $ 是否能被涂上颜色 $ 1 $。
**题目描述**
Doremy有两个数组 $ a $ 和 $ b $，每个数组有 $ n $ 个整数，以及一个整数 $ k $。
最初，她有一个数轴，上面没有整数被着色。她选择一个排列 $ p $，然后执行 $ n $ 个动作。在第 $ i $ 个动作中，她执行以下操作：
- 在数轴上选择一个未着色的整数 $ x $，满足以下条件之一：
- $ x \leq a_{p_i} $；
- 存在一个着色的整数 $ y $ 使得 $ y \leq a_{p_i} $ 且 $ x \leq y + b_{p_i} $。
- 用颜色 $ p_i $ 着色整数 $ x $。
确定整数 $ k $ 是否可以用颜色 $ 1 $ 着色。
**输入输出格式**
**输入格式**
输入由多个测试用例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。测试用例的描述如下。
第一行包含两个整数 $ n $ 和 $ k $（$ 1 \leq n \leq 10^5 $，$ 1 \leq k \leq 10^9 $）。
接下来的 $ n $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \leq a_i, b_i \leq 10^9 $）。
保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。
**输出格式**
对于每个测试用例，如果点 $ k $ 可以用颜色 $ 1 $ 着色，输出“YES”（不带引号）。否则，输出“NO”（不带引号）。
你可以以任何大小写输出“YES”和“NO”（例如，字符串“yEs”、“yes”和“Yes”将被识别为肯定响应）。
**输入输出样例**
**输入样例 #1**
```
6
4 16
5 3
8 12
10 7
15 1
4 16
8 12
10 7
15 1
5 3
4 16
10 7
15 1
5 3
8 12
4 16
15 1
5 3
8 12
10 7
1 1000000000
500000000 500000000
2 1000000000
1 999999999
1 1
```
**输出样例 #1**
```
NO
YES
YES
YES
NO
YES
```
**说明**
对于第一个测试用例，不可能用颜色 $ 1 $ 着色点 $ 16 $。
对于第二个测试用例，$ p=[2,1,3,4] $ 是一种可能的选择，具体细节如下。
- 在第一步，选择 $ x=8 $ 并用颜色 $ 2 $ 着色，因为 $ x=8 $ 未着色且 $ x \leq a_2 $。
- 在第二步，选择 $ x=16 $ 并用颜色 $ 1 $ 着色，因为存在一个着色的点 $ y=8 $ 使得 $ y \leq a_1 $ 且 $ x \leq y + b_1 $。
- 在第三步，选择 $ x=0 $ 并用颜色 $ 3 $ 着色，因为 $ x=0 $ 未着色且 $ x \leq a_3 $。
- 在第四步，选择 $ x=-2 $ 并用颜色 $ 4 $ 着色，因为 $ x=-2 $ 未着色且 $ x \leq a_4 $。
- 最后，点 $ -2, 0, 8, 16 $ 分别用颜色 $ 4, 3, 2, 1 $ 着色。
对于第三个测试用例，$ p=[2,1,4,3] $**题意翻译** 给定两个长度为 $ n $ 的序列 $ a, b $，和一个整数 $ k $，还有一个没有整数着色的数轴。 你需要找到一个长度为 $ n $ 的排列 $ p $，然后执行 $ n $ 次操作。 对于第 $ i $ 次操作，你需要找到一个整数 $ x $ 满足 $ x \leq a_{p_i} $ 或者存在一个已经涂色的正数 $ y $ 使得 $ y \leq a_{p_i} $ 且 $ x \leq y + b_{p_i} $，然后将 $ x $ 涂上颜色 $ p_i $。 判断 $ k $ 是否能被涂上颜色 $ 1 $。 **题目描述** Doremy有两个数组 $ a $ 和 $ b $，每个数组有 $ n $ 个整数，以及一个整数 $ k $。 最初，她有一个数轴，上面没有整数被着色。她选择一个排列 $ p $，然后执行 $ n $ 个动作。在第 $ i $ 个动作中，她执行以下操作： - 在数轴上选择一个未着色的整数 $ x $，满足以下条件之一： - $ x \leq a_{p_i} $； - 存在一个着色的整数 $ y $ 使得 $ y \leq a_{p_i} $ 且 $ x \leq y + b_{p_i} $。 - 用颜色 $ p_i $ 着色整数 $ x $。 确定整数 $ k $ 是否可以用颜色 $ 1 $ 着色。 **输入输出格式** **输入格式** 输入由多个测试用例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。测试用例的描述如下。 第一行包含两个整数 $ n $ 和 $ k $（$ 1 \leq n \leq 10^5 $，$ 1 \leq k \leq 10^9 $）。 接下来的 $ n $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \leq a_i, b_i \leq 10^9 $）。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **输出格式** 对于每个测试用例，如果点 $ k $ 可以用颜色 $ 1 $ 着色，输出“YES”（不带引号）。否则，输出“NO”（不带引号）。 你可以以任何大小写输出“YES”和“NO”（例如，字符串“yEs”、“yes”和“Yes”将被识别为肯定响应）。 **输入输出样例** **输入样例 #1** ``` 6 4 16 5 3 8 12 10 7 15 1 4 16 8 12 10 7 15 1 5 3 4 16 10 7 15 1 5 3 8 12 4 16 15 1 5 3 8 12 10 7 1 1000000000 500000000 500000000 2 1000000000 1 999999999 1 1 ``` **输出样例 #1** ``` NO YES YES YES NO YES ``` **说明** 对于第一个测试用例，不可能用颜色 $ 1 $ 着色点 $ 16 $。 对于第二个测试用例，$ p=[2,1,3,4] $ 是一种可能的选择，具体细节如下。 - 在第一步，选择 $ x=8 $ 并用颜色 $ 2 $ 着色，因为 $ x=8 $ 未着色且 $ x \leq a_2 $。 - 在第二步，选择 $ x=16 $ 并用颜色 $ 1 $ 着色，因为存在一个着色的点 $ y=8 $ 使得 $ y \leq a_1 $ 且 $ x \leq y + b_1 $。 - 在第三步，选择 $ x=0 $ 并用颜色 $ 3 $ 着色，因为 $ x=0 $ 未着色且 $ x \leq a_3 $。 - 在第四步，选择 $ x=-2 $ 并用颜色 $ 4 $ 着色，因为 $ x=-2 $ 未着色且 $ x \leq a_4 $。 - 最后，点 $ -2, 0, 8, 16 $ 分别用颜色 $ 4, 3, 2, 1 $ 着色。 对于第三个测试用例，$ p=[2,1,4,3] $
给定两个长度为 $ n $ 的序列 $ a, b $，和一个整数 $ k $，还有一个没有整数着色的数轴。
你需要找到一个长度为 $ n $ 的排列 $ p $，然后执行 $ n $ 次操作。
对于第 $ i $ 次操作，你需要找到一个整数 $ x $ 满足 $ x \leq a_{p_i} $ 或者存在一个已经涂色的正数 $ y $ 使得 $ y \leq a_{p_i} $ 且 $ x \leq y + b_{p_i} $，然后将 $ x $ 涂上颜色 $ p_i $。
判断 $ k $ 是否能被涂上颜色 $ 1 $。
**题目描述**
Doremy有两个数组 $ a $ 和 $ b $，每个数组有 $ n $ 个整数，以及一个整数 $ k $。
最初，她有一个数轴，上面没有整数被着色。她选择一个排列 $ p $，然后执行 $ n $ 个动作。在第 $ i $ 个动作中，她执行以下操作：
- 在数轴上选择一个未着色的整数 $ x $，满足以下条件之一：
- $ x \leq a_{p_i} $；
- 存在一个着色的整数 $ y $ 使得 $ y \leq a_{p_i} $ 且 $ x \leq y + b_{p_i} $。
- 用颜色 $ p_i $ 着色整数 $ x $。
确定整数 $ k $ 是否可以用颜色 $ 1 $ 着色。
**输入输出格式**
**输入格式**
输入由多个测试用例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。测试用例的描述如下。
第一行包含两个整数 $ n $ 和 $ k $（$ 1 \leq n \leq 10^5 $，$ 1 \leq k \leq 10^9 $）。
接下来的 $ n $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \leq a_i, b_i \leq 10^9 $）。
保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。
**输出格式**
对于每个测试用例，如果点 $ k $ 可以用颜色 $ 1 $ 着色，输出“YES”（不带引号）。否则，输出“NO”（不带引号）。
你可以以任何大小写输出“YES”和“NO”（例如，字符串“yEs”、“yes”和“Yes”将被识别为肯定响应）。
**输入输出样例**
**输入样例 #1**
```
6
4 16
5 3
8 12
10 7
15 1
4 16
8 12
10 7
15 1
5 3
4 16
10 7
15 1
5 3
8 12
4 16
15 1
5 3
8 12
10 7
1 1000000000
500000000 500000000
2 1000000000
1 999999999
1 1
```
**输出样例 #1**
```
NO
YES
YES
YES
NO
YES
```
**说明**
对于第一个测试用例，不可能用颜色 $ 1 $ 着色点 $ 16 $。
对于第二个测试用例，$ p=[2,1,3,4] $ 是一种可能的选择，具体细节如下。
- 在第一步，选择 $ x=8 $ 并用颜色 $ 2 $ 着色，因为 $ x=8 $ 未着色且 $ x \leq a_2 $。
- 在第二步，选择 $ x=16 $ 并用颜色 $ 1 $ 着色，因为存在一个着色的点 $ y=8 $ 使得 $ y \leq a_1 $ 且 $ x \leq y + b_1 $。
- 在第三步，选择 $ x=0 $ 并用颜色 $ 3 $ 着色，因为 $ x=0 $ 未着色且 $ x \leq a_3 $。
- 在第四步，选择 $ x=-2 $ 并用颜色 $ 4 $ 着色，因为 $ x=-2 $ 未着色且 $ x \leq a_4 $。
- 最后，点 $ -2, 0, 8, 16 $ 分别用颜色 $ 4, 3, 2, 1 $ 着色。
对于第三个测试用例，$ p=[2,1,4,3] $**题意翻译** 给定两个长度为 $ n $ 的序列 $ a, b $，和一个整数 $ k $，还有一个没有整数着色的数轴。 你需要找到一个长度为 $ n $ 的排列 $ p $，然后执行 $ n $ 次操作。 对于第 $ i $ 次操作，你需要找到一个整数 $ x $ 满足 $ x \leq a_{p_i} $ 或者存在一个已经涂色的正数 $ y $ 使得 $ y \leq a_{p_i} $ 且 $ x \leq y + b_{p_i} $，然后将 $ x $ 涂上颜色 $ p_i $。 判断 $ k $ 是否能被涂上颜色 $ 1 $。 **题目描述** Doremy有两个数组 $ a $ 和 $ b $，每个数组有 $ n $ 个整数，以及一个整数 $ k $。 最初，她有一个数轴，上面没有整数被着色。她选择一个排列 $ p $，然后执行 $ n $ 个动作。在第 $ i $ 个动作中，她执行以下操作： - 在数轴上选择一个未着色的整数 $ x $，满足以下条件之一： - $ x \leq a_{p_i} $； - 存在一个着色的整数 $ y $ 使得 $ y \leq a_{p_i} $ 且 $ x \leq y + b_{p_i} $。 - 用颜色 $ p_i $ 着色整数 $ x $。 确定整数 $ k $ 是否可以用颜色 $ 1 $ 着色。 **输入输出格式** **输入格式** 输入由多个测试用例组成。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。测试用例的描述如下。 第一行包含两个整数 $ n $ 和 $ k $（$ 1 \leq n \leq 10^5 $，$ 1 \leq k \leq 10^9 $）。 接下来的 $ n $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $（$ 1 \leq a_i, b_i \leq 10^9 $）。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **输出格式** 对于每个测试用例，如果点 $ k $ 可以用颜色 $ 1 $ 着色，输出“YES”（不带引号）。否则，输出“NO”（不带引号）。 你可以以任何大小写输出“YES”和“NO”（例如，字符串“yEs”、“yes”和“Yes”将被识别为肯定响应）。 **输入输出样例** **输入样例 #1** ``` 6 4 16 5 3 8 12 10 7 15 1 4 16 8 12 10 7 15 1 5 3 4 16 10 7 15 1 5 3 8 12 4 16 15 1 5 3 8 12 10 7 1 1000000000 500000000 500000000 2 1000000000 1 999999999 1 1 ``` **输出样例 #1** ``` NO YES YES YES NO YES ``` **说明** 对于第一个测试用例，不可能用颜色 $ 1 $ 着色点 $ 16 $。 对于第二个测试用例，$ p=[2,1,3,4] $ 是一种可能的选择，具体细节如下。 - 在第一步，选择 $ x=8 $ 并用颜色 $ 2 $ 着色，因为 $ x=8 $ 未着色且 $ x \leq a_2 $。 - 在第二步，选择 $ x=16 $ 并用颜色 $ 1 $ 着色，因为存在一个着色的点 $ y=8 $ 使得 $ y \leq a_1 $ 且 $ x \leq y + b_1 $。 - 在第三步，选择 $ x=0 $ 并用颜色 $ 3 $ 着色，因为 $ x=0 $ 未着色且 $ x \leq a_3 $。 - 在第四步，选择 $ x=-2 $ 并用颜色 $ 4 $ 着色，因为 $ x=-2 $ 未着色且 $ x \leq a_4 $。 - 最后，点 $ -2, 0, 8, 16 $ 分别用颜色 $ 4, 3, 2, 1 $ 着色。 对于第三个测试用例，$ p=[2,1,4,3] $