問題一覧 > 通常問題

No.759 悪くない忘年会にしような!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : matsu7874matsu7874 / テスター : はむこはむこ
1 ProblemId : 2586 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-12-06 09:34:02

問題文

あなたは忘年会の飲食店探しをしていますが、世の中には多くの飲食店があり、全てを見ていては時間が足りません。
飲食店$i (1 \le i \le N)$の価格の評価値$P_i$, 滞在可能時間の評価値$T_i$, 口コミの評価値$R_i$の3軸について、データを持っており、これを利用して確認すべき飲食店の数を減らそうと考えました。

1,2,3のいずれかが成り立っているとき、飲食店$j$が飲食店$i$の下位互換であるといいます。
1. $ P_j \lt P_i$かつ$T_j \le T_i$かつ$R_j \le R_i$
2. $ P_j \le P_i$かつ$T_j \lt T_i$かつ$R_j \le R_i$
3. $ P_j \le P_i$かつ$T_j \le T_i$かつ$R_j \lt R_i$

いずれの飲食店の下位互換になっていない飲食店を昇順に列挙してください。

※C++, RustでACできることを確認しています。PyPyではwriterはACできていません。

入力

$N$
$P_1\ T_1\ R_1$
$P_i\ T_i\ R_i$
$P_N\ T_N\  R_N$

1行目にお店の数$N$、
$i+1$行目にお店$i (1 \le i \le N)$の価格の評価値$P_i$, 滞在可能時間の評価値$T_i$, 口コミの評価値$R_i$が半角スペース区切りで与えられます。

$ 1 \le N \le 10^5$
$ 0 \le P_i,T_i, R_i \le 10^4$
$ i \ne j \Leftrightarrow (P_i, T_i, R_i) \ne (P_j, T_j, R_j)$

出力

最後に改行してください。

サンプル

サンプル1
入力
5
5 2 1
4 4 4
3 3 1
0 0 1
5 8 0
出力
1
2
5

店3は店2の、店4は店1,2,3の下位互換であるため除外します。

サンプル2
入力
3
1 0 0
0 1 0
0 0 1
出力
1
2
3

サンプル3
入力
3
1 1 1
2 3 4
5 5 5
出力
3

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。