Overview

For all \(N\) members of a group to ride a certain attraction, the “shortest person” in the group must clear the height restriction. This problem asks us to find the minimum height in the group and count the number of attractions whose height restriction is at or below that value.

Analysis

The condition for all group members to ride attraction \(i\) is that \(S_i \leq L_j\) holds for all \(j\).

If we try to check this straightforwardly, the process becomes “for each attraction, check everyone’s height,” which requires a nested loop. However, looking at the constraints, since \(N, M \leq 2 \times 10^5\), a simple nested loop approach (with time complexity \(O(N \times M)\)) will not meet the time limit.

Let us reorganize the condition. “Everyone’s height is at least \(S_i\)” can be rephrased as “the minimum height in the group is at least \(S_i\)”. In other words, if we let \(L_{min}\) be the minimum height in the group, the condition for all members to ride attraction \(i\) is: $\(S_i \leq L_{min}\)$

Once we compute \(L_{min}\), each attraction only requires a single comparison, which greatly improves efficiency.

Algorithm

1. Find the minimum value \(L_{min}\) from the list of member heights \(L\).
2. Check the list of attraction height restrictions \(S\) in order.
3. Count the number of attractions satisfying \(S_i \leq L_{min}\).
4. Output the count.

Complexity

• Time complexity: \(O(N + M)\)
  • Computing the minimum height takes \(O(N)\), and checking each attraction takes \(O(M)\).
• Space complexity: \(O(N + M)\)
  • This is the memory required to store the input heights and restrictions in lists.

Implementation Notes

• Efficient input: Since \(N\) and \(M\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Finding the minimum: By using Python’s built-in min() function, we can concisely find the minimum value in a list in \(O(N)\).

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: グループの人数, M: アトラクションの数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # L: メンバーの身長
    l_list = list(map(int, input_data[2:2+n]))
    # S: アトラクションの身長制限
    s_list = list(map(int, input_data[2+n:2+n+m]))
    
    # グループ全員が乗るためには、グループ内の最小身長が
    # アトラクションの身長制限以上である必要がある
    min_height = min(l_list)
    
    # 身長制限がグループの最小身長以下のものをカウントする
    ans = 0
    for s in s_list:
        if s <= min_height:
            ans += 1
            
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

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