概要

価格と美味しさの条件を満たす商品の中から、（価格が最小 → 美味しさが最大 → 番号が最小）の優先順位で最適な商品番号を求める問題です。

考察

この問題でやることは大きく2つです。

1. 条件を満たすかの判定
   各商品について

   • \(L \le P_i \le R\)
   • \(S_i \ge T\)
     を両方満たすかを確認します。

2. 条件を満たす商品の中で「最良」を選ぶ
   選び方の優先順位は次の通りです。

   1. 価格が最も安い（\(P\) 最小）
   2. 価格が同じなら美味しさが最も高い（\(S\) 最大）
   3. それでも同じなら番号が最も小さい（\(i\) 最小）

ここで重要な気づきは、全商品を1回見るだけで最良を更新していけば十分ということです。
\(N \le 2\times 10^5\) なので、全探索（\(O(N)\)）は余裕で間に合います。一方、条件を満たす商品を集めてソートする方法も可能ですが、\(O(N\log N)\) と不要に重くなります（また実装も少し複雑になります）。

具体例として、条件を満たす商品が以下の3つだったとします：

最安は価格100の2つ（番号2と5）。その中で美味しさ最大は番号5（\(S=70\)）なので答えは5、となります。

アルゴリズム

1. best を「まだ見つかっていない」として初期化する。
2. \(i=1\) から \(N\) まで順に各商品 \((P_i, S_i)\) を読む。
3. 条件 \(L \le P_i \le R\) かつ \(S_i \ge T\) を満たす場合だけ候補とする。
4. 候補の比較キーを (P, -S, i) とする。
   • P を小さいほど良い（最安）
   • -S を小さいほど良い ⇔ S が大きいほど良い（最大美味しさ）
   • i を小さいほど良い（最小番号）
5. best が未設定、または候補キーが best より小さければ更新する。
6. 最後に best が存在すればその番号、なければ -1 を出力する。

Pythonのタプルは辞書式順序で比較されるため、(P, -S, i) をそのまま比較するだけで要求通りの優先順位が実現できます。

計算量

• 時間計算量: \(O(N)\)（全商品を1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（最良候補を保持するだけ）

実装のポイント

• 「美味しさ最大」をタプル比較で扱いやすくするために、-S を使って 最小化問題に変換しています。

• best = None のようにしておき、最初に条件を満たす商品が出たときに設定するのが簡潔です。

• 入力が最大 \(2\times 10^5\) 行あるため、sys.stdin.readline を使うと安定して高速に読めます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, L, R, T = map(int, input().split())
    best = None  # (P, -S, idx)
    for i in range(1, N + 1):
        P, S = map(int, input().split())
        if L <= P <= R and S >= T:
            cand = (P, -S, i)
            if best is None or cand < best:
                best = cand
    print(best[2] if best is not None else -1)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。