分数: 500 点
问题陈述
两段 [L_1:R_1] 和 [L_2:R_2] 据说 相交 当 L_1 \leq R_2 和 L_2 \leq R_1 成立。
考虑以下问题 P:
Input: N segments [L_1: R_1], \cdots, [L_N:R_N]
L_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_N are pairwise distinct.
Output: the maximum number of segments that can be chosen so that no two of them intersect.
Takahashi 实施了一个程序,其工作原理如下:
Sort the given segments in the increasing order of R_i and let the result be [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}].
For each i = 1, 2, \cdots , N, do the following:
Choose [L_{p_i}:R_{p_i}] if it intersects with none of the segments chosen so far.
Print the number of chosen segments.
另一方面,青木实施了一个程序,其工作原理如下:
Sort the given segments in the increasing order of L_i and let the result be [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}].
For each i = 1, 2, \cdots , N, do the following:
Choose [L_{p_i}:R_{p_i}] if it intersects with none of the segments chosen so far.
Print the number of chosen segments.
给定的是整数 N 和 M。构建问题的输入 P,包括 N 段,使得以下内容成立:
$$ (\text{高桥程序打印的值}) - (\text{青木程序打印的值}) = M $$
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 2 \times 10^5
- -N \leq M \leq N
输入
输入由标准输入按以下格式给出:
N M
输出
如果没有设置 N 满足条件的段,打印 -1.
否则,打印 N 行如下:
L_1 R_1 L_2 R_2 \vdots L_N R_N
在这里, [L_1:R_1], \cdots, [L_N:R_N] 必须满足以下条件:
- 1 \leq L_i < R_i \leq 10^9
- L_i \neq L_j (i \neq j)
- R_i \neq R_j (i \neq j)
- L_i \neq R_j
- L_1, \cdots , L_N , R_1, \cdots , R_N 是整数(添加 21:46)
如果有多个答案,则接受其中任何一个。
请务必在输出末尾打印换行符。
示例输入 1
5 1
示例输出 1
1 10 8 12 13 20 11 14 2 4
我们将这五个段称为 Segment 1,段 2, \cdots,段 5.
Takahashi 的程序将按如下方式运行:
Rearrange the segments into the order Segment 5, Segment 1, Segment 2, Segment 4, Segment 3. Choose Segment 5. Skip Segment 1 (because it intersects with Segment 5). Choose Segment 2. Skip Segment 4 (because it intersects with Segment 2). Choose Segment 3.
因此,高桥的程序将打印 3.
青木的程序将按如下方式工作:
Rearrange the segments into the order Segment 1, Segment 5, Segment 2, Segment 4, Segment 3. Choose Segment 1. Skip Segment 5 (because it intersects with Segment 1). Skip Segment 2 (because it intersects with Segment 1). Choose Segment 4. Skip Segment 3 (because it intersects with Segment 4).
因此,Aoki 的程序将打印 2.
在这里,我们有 3 - 2 = 1 \left(= M \right),因此这五个段满足条件。
示例输入 2
10 -10
示例输出 2
-1