AT_abc155_f [ABC155F] Perils in Parallel

题目描述

由于 AlDebaran 王国的入侵，AtCoder 王国各地被安放了炸弹。

幸运的是，得益于 AtCoder 王国 ABC 队的英勇奋战，部分控制装置被夺回，你决定利用这些装置尝试解除炸弹。

共有 $N$ 个炸弹，编号为 $1$ 到 $N$。第 $i$ 个炸弹位于坐标 $A_i$，当 $B_i=1$ 时其电源为开启，$B_i=0$ 时为关闭。

控制装置上有 $M$ 根导线，编号为 $1$ 到 $M$。切断第 $j$ 根导线时，所有坐标在 $L_j$ 到 $R_j$ 之间（包含端点）的炸弹，其电源状态会被切换（开变关，关变开）。

请判断是否存在一种切断导线的方式，使得所有炸弹的电源都关闭。如果存在，请输出一种可行的导线组合。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $A_1$ $B_1$ : $A_N$ $B_N$ $L_1$ $R_1$ : $L_M$ $R_M$

输出格式

如果无法使所有炸弹的电源都关闭，输出 -1。

如果可以，请输出一组可行的导线组合，格式如下：

$k$ $c_1$ $c_2$ $\dots$ $c_k$

其中，$k$ 表示需要切断的导线数量（可以为 $0$），$c_1,\ c_2,\ \dots,\ c_k$ 表示切断的导线编号，需满足 $1\leq c_1 < c_2 < \dots < c_k \leq M$。

输入输出样例 #1

输入 #1

3 4
5 1
10 1
8 0
1 10
4 5
6 7
8 9

输出 #1

2
1 4

输入输出样例 #2

输入 #2

4 2
2 0
3 1
5 1
7 0
1 4
4 7

输出 #2

-1

输入输出样例 #3

输入 #3

3 2
5 0
10 0
8 0
6 9
66 99

输出 #3

0

输入输出样例 #4

输入 #4

12 20
536130100 1
150049660 1
79245447 1
132551741 0
89484841 1
328129089 0
623467741 0
248785745 0
421631475 0
498966877 0
43768791 1
112237273 0
21499042 142460201
58176487 384985131
88563042 144788076
120198276 497115965
134867387 563350571
211946499 458996604
233934566 297258009
335674184 555985828
414601661 520203502
101135608 501051309
90972258 300372385
255474956 630621190
436210625 517850028
145652401 192476406
377607297 520655694
244404406 304034433
112237273 359737255
392593015 463983307
150586788 504362212
54772353 83124235

输出 #4

5
1 7 8 9 11

说明/提示

限制条件

• 所有输入均为整数。
• $1\leq N\leq 10^5$
• $1\leq A_i\leq 10^9\ (1\leq i\leq N)$
• $A_i$ 互不相同
• $B_i$ 仅为 $0$ 或 $1\ (1\leq i\leq N)$
• $1\leq M\leq 2\times 10^5$
• $1\leq L_j\leq R_j\leq 10^9\ (1\leq j\leq M)$

样例解释 1

坐标 $5,\ 10$ 的炸弹电源为开启，坐标 $8$ 的炸弹电源为关闭。切断导线 $1$ 时，坐标在 $1$ 到 $10$ 之间的所有炸弹（即全部炸弹）电源会切换。切断导线 $4$ 时，坐标在 $8$ 到 $9$ 之间的炸弹（即炸弹 $3$）电源会切换。因此，切断导线 $1$ 和 $4$ 共 $2$ 根，可以使所有炸弹电源关闭。

样例解释 2

无论如何选择切断的导线，都无法使所有炸弹电源关闭。

样例解释 3

一开始所有炸弹电源均为关闭，因此无需切断任何导线。

样例解释 4

如果存在多组满足条件的导线组合，输出任意一组均可。

由 ChatGPT 4.1 翻译