分数: 350 点
问题陈述
高桥有 N 纸牌游戏“AtCoder Magics”中的纸牌。的 i第一张牌将被称为牌 i。每张卡都有两个参数:强度和成本。卡 i 的实力为 A_i 和成本 C_i.
他不喜欢弱牌,所以他会丢弃它们。具体来说,他会重复执行以下操作,直到无法再执行为止:
- 选择两张牌 x 和 y 这样 A_x > A_y 和 C_x < C_y。丢弃卡 y.
可以证明,无法再进行操作时剩余的牌组是唯一确定的。找到这组卡片。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i, C_i \leq 10^9
- A_1, A_2, \dots ,A_N 都是不同的。
- C_1, C_2, \dots ,C_N 都是不同的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 C_1 A_2 C_2 \vdots A_N C_N
输出
要有 m 剩余的牌,牌 i_1, i_2, \dots, i_m,按升序排列。按以下格式打印这些内容:
m i_1 i_2 \cdots i_m
示例输入 1
3 2 4 1 1 3 2
示例输出 1
2 2 3
专注于卡片 1 和 3,我们有 A_1 < A_3 和 C_1 > C_3,所以卡 1 可以被丢弃。
无法执行进一步的操作。此时,卡 2 和 3 剩余,因此打印它们。
示例输入 2
5 1 1 10 2 100 3 1000 4 10000 5
示例输出 2
5 1 2 3 4 5
在这种情况下,不能丢弃任何牌。
示例输入 3
6 32 101 65 78 2 29 46 55 103 130 52 40
示例输出 3
4 2 3 5 6