103542: [Atcoder]ABC354 C - AtCoder Magics

Problem Statement

Takahashi has $N$ cards from the card game "AtCoder Magics." The $i$-th card will be called card $i$. Each card has two parameters: strength and cost. Card $i$ has a strength of $A_i$ and a cost of $C_i$.

He does not like weak cards, so he will discard them. Specifically, he will repeat the following operation until it can no longer be performed:

• Choose two cards $x$ and $y$ such that $A_x > A_y$ and $C_x < C_y$. Discard card $y$.

It can be proved that the set of remaining cards when the operations can no longer be performed is uniquely determined. Find this set of cards.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, C_i \leq 10^9$
• $A_1, A_2, \dots ,A_N$ are all distinct.
• $C_1, C_2, \dots ,C_N$ are all distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $C_1$
$A_2$ $C_2$
$\vdots$
$A_N$ $C_N$

Output

Let there be $m$ remaining cards, cards $i_1, i_2, \dots, i_m$, in ascending order. Print these in the following format:

$m$
$i_1$ $i_2$ $\cdots$ $i_m$

Sample Input 1

3
2 4
1 1
3 2

Sample Output 1

2
2 3

Focusing on cards $1$ and $3$, we have $A_1 < A_3$ and $C_1 > C_3$, so card $1$ can be discarded.

No further operations can be performed. At this point, cards $2$ and $3$ remain, so print them.

Sample Input 2

5
1 1
10 2
100 3
1000 4
10000 5

Sample Output 2

5
1 2 3 4 5

In this case, no cards can be discarded.

Sample Input 3

6
32 101
65 78
2 29
46 55
103 130
52 40

Sample Output 3

4
2 3 5 6

问题描述

高桥持有卡牌游戏"AtCoder Magics"中的$N$张卡牌。第$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