Overview

Given \(N\) products, find the product that satisfies conditions on price and tastiness, selecting the one with the lowest price (if tied, the highest tastiness; if still tied, the smallest index).

Analysis

For this problem, we need to check the following three conditions for each product:

1. The price is at least \(L\) and at most \(R\)
2. The tastiness is at least \(T\)
3. Among those satisfying the above, select the optimal one with priority: “minimum price → maximum tastiness → minimum index”

Since the number of products \(N\) is at most \(2 \times 10^5\), an \(O(N)\) solution that examines each product once is more than sufficient. No additional processing such as sorting is needed — the answer can be found in a single linear scan.

Algorithm

We solve this using linear scanning with comparison keys.

For each product \(i\), we check whether it satisfies the conditions (\(L \leq P_i \leq R\) and \(S_i \geq T\)), and if so, compare it with the current best product found so far.

The comparison priorities are as follows:

1. Smaller price \(P_i\) is better
2. If prices are equal, larger tastiness \(S_i\) is better
3. If those are also equal, smaller index \(i\) is better

We achieve this using lexicographic comparison of tuples. Specifically, for each product we create the key \((P_i, -S_i, i)\).

• \(P_i\): smaller is better → ascending order as-is
• \(-S_i\): larger tastiness means smaller \(-S_i\) → ascending comparison achieves descending order of tastiness
• \(i\): smaller is better → ascending order as-is

By selecting the tuple that is lexicographically smallest, we correctly reflect all priority levels.

Concrete example: Consider \(N=3, L=100, R=500, T=3\) with the following products:

Product Index	Price	Tastiness	Satisfies Conditions?	Key
1	200	5	○	\((200, -5, 1)\)
2	200	8	○	\((200, -8, 2)\)
3	300	10	○	\((300, -10, 3)\)

By lexicographic comparison of keys, \((200, -8, 2) < (200, -5, 1) < (300, -10, 3)\), so the answer is product \(2\) (among the products with the same price of 200 yen, tastiness 8 is the maximum).

Complexity

• Time complexity: \(O(N)\) — just a single scan through all products
• Space complexity: \(O(N)\) — for reading input data (the variable itself for tracking the best product is \(O(1)\))

Implementation Notes

• By leveraging lexicographic comparison of tuples, the three-level priority can be handled simply with a single comparison (key < best). The key trick is negating the tastiness (-S).

• Using sys.stdin.read() to read all input at once ensures fast operation even when \(N\) is large.

• Don’t forget to output -1 when no product satisfying the conditions is found (best is None).

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    L = int(input_data[idx]); idx += 1
    R = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    best = None  # (price, -tastiness, index)
    
    for i in range(1, N + 1):
        P = int(input_data[idx]); idx += 1
        S = int(input_data[idx]); idx += 1
        
        if L <= P <= R and S >= T:
            key = (P, -S, i)
            if best is None or key < best:
                best = key
    
    if best is None:
        print(-1)
    else:
        print(best[2])

main()

---

This editorial was generated by claude4.6opus-thinking.