Overview

Given \(N\) products, find the product number that best “matches the conditions” among those satisfying the specified price range \([L, R]\) and having a deliciousness of at least \(T\).

Analysis

The most important aspects of this problem are organizing the priority of “which product takes highest precedence” and efficiently processing a large amount of data.

1. Organizing Priorities

When multiple products satisfy the conditions, narrow down to one using the following priorities: 1. Lowest price 2. If prices are the same, highest deliciousness 3. If both price and deliciousness are the same, smallest product number

2. Condition Checking

For each product \((P_i, S_i)\), check whether all of the following conditions are satisfied: - \(L \leq P_i \leq R\) - \(S_i \geq T\)

3. Updating the Optimal Product

When examining products sequentially from the \(1\)st onward, maintain a tentative “best product.” Update only when a new product satisfies the conditions and is better than the “tentative best product” (lower price, or same price with higher deliciousness).

Regarding the condition of outputting the smallest product number, by scanning products in order of their number (\(1, 2, \dots, N\)) and not updating in case of a tie, the “smallest numbered” product naturally remains.

Algorithm

1. Initialize the optimal product number best_idx to -1, its price best_p to infinity, and deliciousness best_s to -1.
2. For each product \(i = 1, 2, \dots, N\), repeat the following:
   • If \(L \leq P_i \leq R\) and \(S_i \geq T\):
     • No product satisfying the conditions has been found yet (best_idx == -1)
     • Or, the current product’s price is cheaper (\(P_i < \text{best\_p}\))
     • Or, the price is the same but deliciousness is higher (\(P_i = \text{best\_p}\) and \(S_i > \text{best\_s}\))
     • If any of the above is satisfied, update best_idx, best_p, and best_s.
3. Output the final best_idx.

Complexity

• Time complexity: \(O(N)\)
  • For \(N\) products, each product is checked exactly once, so the loop runs \(N\) times. Since \(N \leq 2 \times 10^5\), this runs sufficiently fast.
• Space complexity: \(O(N)\)
  • If all input values are stored in lists, memory proportional to the number of products is used.

Implementation Notes

• Fast input processing: In Python, when \(N\) exceeds \(10^5\), reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input().

• Setting initial values: When finding a minimum, it is standard practice to set the initial value to a very large number (such as float('inf')), and when finding a maximum, to a very small number (such as -1).

• Index adjustment: Product numbers in the problem start from \(1\), but loops and lists in programming languages often start from \(0\), so you need to either add +1 when outputting or adjust within the loop.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストに格納します
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # すべてのトークンを整数に変換します
    # 大量のデータを扱う場合、一括で変換する方が個別に変換するより高速な傾向があります
    nums = list(map(int, input_data))
    
    # 基本情報の取得
    N = nums[0]
    L = nums[1]
    R = nums[2]
    T = nums[3]
    
    # 最適な商品の情報を保持する変数
    # best_idx: 商品番号, best_p: 値段, best_s: 美味しさ
    best_idx = -1
    best_p = float('inf')
    best_s = -1
    
    # 各商品を順番にチェックします
    # 商品iの値段Piはnums[4 + 2*i]、美味しさSiはnums[5 + 2*i]に格納されています
    for i in range(N):
        p = nums[4 + 2*i]
        s = nums[5 + 2*i]
        
        # 条件1: 値段がL以上R以下
        # 条件2: 美味しさがT以上
        if L <= p <= R and s >= T:
            # 以下のいずれかの場合に最適な商品を更新します
            # 1. 条件を満たす商品がまだ見つかっていない
            # 2. 現在の商品の方が値段が安い
            # 3. 値段が同じで、現在の性能（美味しさ）が高い
            # 商品番号が小さいものを優先するという条件は、ループを1からNの順で回し、
            # 同点の場合に更新しないことで自然に満たされます
            if best_idx == -1 or p < best_p or (p == best_p and s > best_s):
                best_idx = i + 1
                best_p = p
                best_s = s
    
    # 結果を出力します
    print(best_idx)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-thinking.