← 返回题目列表

AtCoder · abc354_c

E. AtCoder 魔法

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

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