← 返回题目列表

AtCoder · arc106_c

C. 解决方案

中文机器翻译题面 查看原题

分数: 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