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

**因洛谷限制，本题不予评测每个 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

无

无

#### 样例 #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)。