Overview

Given students lined up in order of their student numbers, a student is defined as a “looking-up student” if there exists a student before them who belongs to the tall group (height \(T\) or more) and whose height is greater than theirs. The problem asks us to find the number of such students.

Analysis

A naive approach would be, for each student \(i\), to check all previous students (\(j < i\)) to see if there exists a student with \(S_j \geq T\) and \(S_j > S_i\). However, this method has a time complexity of \(O(N^2)\), which would result in an extremely long execution time given the constraint that \(N\) can be up to \(10^6\).

An efficient solution is to maintain “the maximum height among tall group students encountered so far” as we scan the sequence from the beginning. For each student \(i\), if the maximum height of the tall group so far is greater than \(S_i\), then that student is a looking-up student. Since the processing for each student takes constant time, this approach solves the problem in linear time.

Algorithm

1. Initialize variable max_so_far to 0 (records the maximum height among tall group students encountered so far)
2. Initialize variable count to 0 (counts the number of looking-up students)
3. Process students from number 1 to N in order:
   • If the current student is not the first one (\(i > 0\)) and max_so_far is greater than the current student’s height:
     • Increment count by 1
   • If the current student belongs to the tall group (\(S_i \geq T\)):
     • Compare max_so_far with the current height and update if necessary (if \(S_i > \text{max\_so\_far}\), set max_so_far = S_i)
4. Output count

In this algorithm, only students in the tall group can update max_so_far, so it always holds “the maximum height among tall group students encountered so far.”

Complexity

• Time complexity: \(O(N)\)
  • Since each of the \(N\) students is processed exactly once
• Space complexity: \(O(N)\)
  • An array is needed to store the height data, but only the space required for reading input

Implementation Notes

• Note that the first student (\(i=0\)) cannot be a looking-up student since there are no students before them

• The initial value of max_so_far is set to 0 (this is fine since all heights are at least 1)

• It is important to perform the tall group check and the maximum value update in the correct order

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    S = list(map(int, data[2:2+n]))
    
    count = 0
    max_so_far = 0
    
    for i in range(n):
        if i > 0 and max_so_far > S[i]:
            count += 1
            
        if S[i] >= T:
            if S[i] > max_so_far:
                max_so_far = S[i]
    
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.