AT_arc106_c [ARC106C] Solutions
题目描述
对于两个区间 $[L_1:R_1],\ [L_2:R_2]$，如果 $L_1 \leq R_2$ 且 $L_2 \leq R_1$，则定义这两个区间*相交*。
考虑如下问题 $P$：
> 输入：$N$ 个区间 $[L_1:R_1],\cdots,[L_N:R_N]$，其中 $L_1,L_2,\cdots,L_N,R_1,R_2,\cdots,R_N$ 均互不相同。
> 输出：可以选择的、任意两个区间都不相交的区间的最大数量。
高桥君实现了如下程序：
> 按照 $R_i$ 的值升序排列输入的区间，得到 $[L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots, [L_{p_N}:R_{p_N}]$。
> 对于 $i=1,2,\cdots,N$，依次进行如下操作：
> 如果 $[L_{p_i}:R_{p_i}]$ 与之前选择的所有区间都不相交，则选择该区间。
> 输出所选择的区间数量。
另一方面，青木君实现了如下程序：
> 按照 $L_i$ 的值升序排列输入的区间，得到 $[L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots, [L_{p_N}:R_{p_N}]$。
> 对于 $i=1,2,\cdots,N$，依次进行如下操作：
> 如果 $[L_{p_i}:R_{p_i}]$ 与之前选择的所有区间都不相交，则选择该区间。
> 输出所选择的区间数量。
给定整数 $N, M$，请构造一个由 $N$ 个区间组成的问题 $P$ 的输入，使得
$$
(\text{高桥君的程序输出的值}) - (\text{青木君的程序输出的值}) = M
$$
输入格式
输入为以下格式，从标准输入读取：
> $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 \leq N \leq 2 \times 10^5$
- $-N \leq M \leq N$
### 样例解释 1
将 $5$ 个区间依次命名为区间 $1$、区间 $2$、$\cdots$、区间 $5$。
高桥君的程序如下操作：
> 将区间按区间 $5$、区间 $1$、区间 $2$、区间 $4$、区间 $3$ 排序。
> 选择区间 $5$。
> 区间 $1$ 不选（与区间 $5$ 相交）。
> 选择区间 $2$。
> 区间 $4$ 不选（与区间 $2$ 相交）。
> 选择区间 $3$。
> 因此，高桥君的程序输出 $3$。
青木君的程序如下操作：
> 将区间按区间 $1$、区间 $5$、区间 $2$、区间 $4$、区间 $3$ 排序。
> 选择区间 $1$。
> 区间 $5$ 不选（与区间 $1$ 相交）。
> 区间 $2$ 不选（与区间 $1$ 相交）。
> 选择区间 $4$。
> 区间 $3$ 不选（与区间 $4$ 相交）。
> 因此，青木君的程序输出 $2$。
此时，$3-2=1(=M)$，这 $5$ 个区间满足条件。
由 ChatGPT 4.1 翻译