Overview

From the products that satisfy the conditions, select the one with the lowest price, then the highest tastiness, and if there is still a tie, the smallest product number.

Analysis

In this problem, we first consider only the products that satisfy both conditions: “price is at least \(L\) yen and at most \(R\) yen” and “tastiness is at least \(T\)”.

Products that do not satisfy these conditions can be completely ignored. If there are no candidates, output -1.

Next, we need to select the “optimal product” from the candidates. The selection criteria are as follows:

1. Lowest price
2. If prices are the same, highest tastiness
3. If those are also the same, smallest product number

Since we need to sort by multiple keys like this, writing a comparison function each time is cumbersome and inefficient.

Instead, we create a list of candidate products and sort them all at once by carefully designing the sort key.

Specifically, by sorting with the tuple \((P, -S, idx)\), we automatically achieve the order “price ascending → tastiness descending → product number ascending”.

Also, since the constraints are very large (\(N\) is up to \(2 \times 10^5\)), efficient input processing is necessary. In Python, this can be sped up by using sys.stdin.read().

Algorithm

1. Read all products and store them as tuples \((P_i, S_i, i)\).
2. Extract only the products satisfying the conditions \(L \leq P_i \leq R\) and \(S_i \geq T\).
3. Sort the extracted product list using \((P_i, -S_i, i)\) as the sort key.
4. Output the index (product number) of the first element after sorting.
5. If no products satisfy the conditions, output -1.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the product list)

Implementation Notes

• sys.stdin.read() is used for fast input.

• By using \((P, -S, idx)\) as the sort key, multi-key sorting with priority is easily achieved.

• Since product numbers are 1-indexed, they are stored as i + 1 in the tuple.

  Source Code

import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    R = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    goods = []
    for i in range(N):
        P = int(data[idx]); idx += 1
        S = int(data[idx]); idx += 1
        goods.append((P, S, i + 1))
    
    # 条件を満たす商品のみをフィルタリング
    valid_goods = [(P, S, idx) for P, S, idx in goods if L <= P <= R and S >= T]
    
    if not valid_goods:
        print(-1)
        return
    
    # 値段が最小 → 美味しさが最大 → 商品番号が最小
    # そのため、(P, -S, idx) の順でソートする
    valid_goods.sort(key=lambda x: (x[0], -x[1], x[2]))
    print(valid_goods[0][2])

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.