Overview

This is a problem where, among products satisfying conditions on price and tastiness, you need to find the optimal product number with the priority order: (minimum price → maximum tastiness → minimum product number).

Approach

There are two main things to do in this problem:

1. Checking whether conditions are satisfied
   For each product, check whether both of the following are satisfied:

   • \(L \le P_i \le R\)
   • \(S_i \ge T\)

2. Selecting the “best” among products that satisfy the conditions
   The priority order for selection is as follows:

   1. Cheapest price (\(P\) minimum)
   2. If prices are the same, highest tastiness (\(S\) maximum)
   3. If still tied, smallest product number (\(i\) minimum)

The key insight here is that it is sufficient to scan through all products once and update the best candidate along the way.
Since \(N \le 2\times 10^5\), a full scan (\(O(N)\)) is more than fast enough. Alternatively, collecting all qualifying products and sorting them is also possible, but it is unnecessarily heavy at \(O(N\log N)\) (and the implementation becomes slightly more complex).

As a concrete example, suppose the following 3 products satisfy the conditions:

The cheapest are the two with price 100 (numbers 2 and 5). Among them, the one with the highest tastiness is number 5 (\(S=70\)), so the answer is 5.

Algorithm

1. Initialize best as “not yet found.”
2. Read each product \((P_i, S_i)\) in order from \(i=1\) to \(N\).
3. Only consider it as a candidate if it satisfies the conditions \(L \le P_i \le R\) and \(S_i \ge T\).
4. Use (P, -S, i) as the comparison key for candidates.
   • Smaller P is better (cheapest)
   • Smaller -S is better ⇔ larger S is better (highest tastiness)
   • Smaller i is better (smallest number)
5. Update best if it is unset or if the candidate’s key is smaller than that of best.
6. At the end, output the product number of best if it exists, otherwise output -1.

Since Python tuples are compared in lexicographic order, simply comparing (P, -S, i) directly achieves the required priority order.

Complexity

• Time complexity: \(O(N)\) (just a single pass through all products)
• Space complexity: \(O(1)\) (only storing the best candidate)

Implementation Notes

• To make “maximum tastiness” easy to handle with tuple comparison, we use -S to convert it into a minimization problem.

• Using something like best = None and setting it when the first qualifying product is found is a clean approach.

• Since the input can have up to \(2\times 10^5\) lines, using sys.stdin.readline ensures stable and fast reading.

  Source Code

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()

This editorial was generated by gpt-5.2-high.