[JOISC 2021 Day4] イベント巡り 2 (Event Hopping 2)

**因洛谷限制，本题不予评测每个 Subtask 的第 1 ~ 20 个测试点，您可以 [点此](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/event2-data.zip) 下载所有数据自行评测或在 [这里](https://www.luogu.com.cn/problem/U159034) 测试，若您希望写本题题解，建议您在通过 [本题](https://www.luogu.com.cn/problem/P7562) 与 [每个 Subtask 前 20 个测试点](https://www.luogu.com.cn/problem/U159034) 之后再写题解。**

IOI Park 将有 $n$ 场活动。 这些活动的编号从 $1$ 到 $n$。 活动 $i$ 从时间 $L_i+10^{-1}$ 到时间 $R_i-10^{-1}$ 举行。数据保证 $L_i$ 和 $R_i$ 是整数。 JOI 君决定参加其中的 $k$ 个活动。但是，JOI 君不能在中间加入或离开每个活动。**在两个活动场所间移动的时间忽略不计**。 JOI 君希望参加编号较小的活动。严格来说，JOI 君参加的 $k$ 个活动的编号依次为 $a_1,\cdots,a_k$，其中 $1 \le a_1 < \cdots < a_k \le n$。如果序列 $(a_1, \cdots, a_k)$ 的编号小于 $(b_1, \cdots, b_k)$，当且仅当存在 $j\ (1 \le j \le k)$ 满足在区间 $[1,j-1]$ 里的所有 $l$ 都有 $a_l=b_l$ 和 $a_j<b_j$。 给出每个活动的信息和 JOI 君参加的活动个数 $k$，判断 JOI 君是否可以参加 $k$ 个活动，如果可以，输出所有的 $k$ 个活动的编号。

第一行，两个正整数 $n,k$。 第 $2 \sim n + 1$ 行，每行 $2$ 个正整数，$L_i, R_i$。

如果 JOI 君可以参加 $k$ 个活动： - 输出 $k$ 行。 - 我们设 JOI 君参与的 $k$ 个活动的编号为 $a_1, a_2, \cdots, a_k\ (1\le a_1 < \cdots < a_k \le n）$，你需要在第 $j$ 行输出 $a_j\ (1\le j \le k)$。 请注意，序列 $(a_1, \cdots, a_k)$ 必须是 **最小字典序**。 如果 JOI 君无法参加 $k$ 个活动，输出 $\texttt{-1}$。

5 4
1 3
2 5
8 9
6 8
10 15

1
3
4
5

4 3
1 4
3 5
4 9
7 10

-1

10 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649

1
2
4
6
7
8

20 16
250732298 258217736
26470443 34965880
252620676 260043105
692063405 697656580
497457675 504191511
391372149 397942668
858168758 867389085
235756850 241022021
585764751 593366541
207824318 217052204
661682908 671226688
886273261 892279963
770109416 778960597
264372562 270395107
176883483 186662376
509929119 519063796
109491630 118520141
162731982 168101507
662727316 668317158
757072772 765493222

1
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#### 样例 #1 解释 有 $2$ 种方式可以参加正好 $4$ 个活动。 - 参加 $1, 3, 4, 5$； - 参加 $2, 3, 4, 5$。 数列 $(1,3,4,5)$ 比数列 $(2, 3, 4, 5)$ 字典序小，所以输出 $1, 3, 4, 5$。 #### 样例 #2 解释 无论怎么选择都不可能正好参加 $3$ 个活动，所以输出 $\tt -1$。 #### 样例 #3 解释 本样例满足所有 Subtask 的条件。 #### 数据规模与约定 **因洛谷限制，本题不予评测每个 Subtask 的第 $1\sim 20$ 个测试点。** **本题采用 Subtask 计分法。** | Subtask | 分值占比百分率 | $n$ | $L_i$ | | :----: | :----: | :----: | :----:| | $1$ | $7\%$ | / | $L_i \le L_{i+1}\ (1 \le i \le n − 1)$ | | $2$ | $1\%$ | $\le20$ | / | | $3$ | $31\%$ | $\le 3 \times 10^3$ |/ | | $4$ | $61\%$ | / | / | **注：斜线表示无特殊限制。** 对于 $100\%$ 的数据： - $1\le n\le 10^5$； - $1 \le k \le n$； - $1\le L_i < R_i \le 10^9 (1\le i \le n)$。 #### 说明 本题译自 [第２０回日本情報オリンピック 2020/2021春季トレーニング合宿 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [競技 4 -](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/2021-sp-d4-notice.pdf) [T1 日文题面](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day4/event2.pdf)。