\(2\) 次元平面にデータをプロットすると、直感的に理解することができます。

以下は入出力例 1 のデータをプロットしたものです。

カード \(x, y\) について \(A_x > A_y\) かつ \(C_x < C_y\) であることは、上の図のように \(2\) 次元平面にプロットしたときに、カード \(x\) に対応する点がカード \(y\) に対応する点の右下にあることと言い換えられます。入出力例 1 では、カード \(3\) に対応する点はカード \(1\) に対応する点の右下にあります。

最後まで消されないカードの条件を考えてみます。上の議論から、自分の点の右下に点がないようなカードは最後まで消されません。逆に、そうでないカードは必ず消されます。

「自分の点の右下に点がない」カードの集合は以下のように求めることができます。コストの小さい点、つまり下の点から順に見ていって、ここまでの最大の強さを更新するもの (一番右にあるもの) のみを答えに入れるイメージです。(最大の強さを更新しないということは、自分よりコストが小さく強さが大きいカードがある、つまり自分より右下にカードがあることに対応します。)

• カードを \(C_i\) を基準に昇順ソートする。はじめ \(v = 0\) とし、 \(S\) は空集合とする。
• \(i = 1, 2, \cdots ,N\) の順に、 \(A_i > v\) であれば \(S\) に \(i\) 番目のカードを追加して \(v\) を \(A_i\) に更新する。
• 最終的な \(S\) が求めるものである。

入出力例 1 では以下のようになります。

• カードの順は \(C_i\) の昇順に \(2, 3, 1\) となる。
  • \(A_2 (= 1) > v (= 0)\) より、 \(S\) にカード \(2\) を追加して \(v = 1\) とする。
  • \(A_3 (= 3) > v (= 1)\) より、 \(S\) にカード \(3\) を追加して \(v = 3\) とする。
  • \(A_1 (= 2) < v (= 3)\) より、カード \(1\) は \(S\) に追加されない。
• 最終的に \(S = \{ 2, 3 \}\) である。

例えば C++ では以下のように実装できます。計算量はソートがボトルネックで \(O(N \log N)\) です。

#include <bits/stdc++.h>

using namespace std;

struct Card {
    int a;
    int c;
    int index;
};

int main() {
    // 入力
    int n;
    cin >> n;
    vector<Card> cards(n);
    for (int i = 0; i < n; ++i) {
        int a, c;
        cin >> a >> c;
        cards[i] = {a, c, i};
    }
    
    // C[i] の昇順にソート
    sort(cards.begin(), cards.end(), [&](const auto &l, const auto &r) {
        return l.c < r.c;
    });
    
    // 答えを求める計算
    vector<int> ans;
    int v = 0;
    for (int i = 0; i < n; ++i) {
        if (cards[i].a > v) {
            v = cards[i].a;
            ans.push_back(cards[i].index);
        }
    }
    sort(ans.begin(), ans.end());
    
    // 出力
    const int m = (int)ans.size();
    cout << m << endl;
    for (int i = 0; i < m; ++i) {
        cout << ans[i] + 1;
        if (i == m - 1) {
            cout << endl;
        } else {
            cout << ' ';
        }
    }
}