Overview

This is a problem where, among \(N\) used cars, we need to count the number of cars whose price falls within a specified range and whose mileage does not exceed a given limit.

Analysis

In this problem, we determine whether each car simultaneously satisfies the following two conditions:

1. Price condition: \(L \leq P_i \leq R\) (the price is at least \(L\) ten-thousand yen and at most \(R\) ten-thousand yen)
2. Mileage condition: \(K_i \leq M\) (the mileage is at most \(M\) km)

For example, when \(L = 50\), \(R = 100\), \(M = 30000\): - A car with price 60 ten-thousand yen and mileage 25000 km → candidate car (satisfies both conditions) - A car with price 40 ten-thousand yen and mileage 20000 km → not a candidate (price is too low) - A car with price 80 ten-thousand yen and mileage 50000 km → not a candidate (mileage is too high)

Since this problem is simply a repeated conditional check, a brute force approach that checks each car one by one is sufficient. Given the constraint \(N \leq 10^5\), each car can be evaluated in \(O(1)\), so it fits within the time limit.

Algorithm

1. Initialize a counter variable count to \(0\)
2. For each of the \(N\) cars, read the price \(P_i\) and mileage \(K_i\)
3. For each car, check whether \(L \leq P_i \leq R\) and \(K_i \leq M\) are both satisfied
4. If the conditions are satisfied, increment count by \(1\)
5. Finally, output count

Complexity

• Time complexity: \(O(N)\)
  • Because we perform a constant-time \(O(1)\) conditional check for each of the \(N\) cars
• Space complexity: \(O(1)\)
  • Because we only store the counter variable and the information of the currently read car

Implementation Notes

• In Python, the expression L <= P <= R concisely represents “\(L\) or more and \(R\) or less.” This is equivalent to L <= P and P <= R.

• To determine whether the conditions are satisfied, we combine the two conditions with and. The entire expression evaluates to True only when both are True.

• Since each car’s information is no longer needed after it is used, we save memory by evaluating directly while reading rather than storing the data in a list.

  Source Code

N, L, R, M = map(int, input().split())
count = 0
for _ in range(N):
    P, K = map(int, input().split())
    if L <= P <= R and K <= M:
        count += 1
print(count)

This editorial was generated by claude4.5opus.