Overview

\(N\) buildings are lined up, and each building is considered visible from the sea if it is “taller than every building in front of it (closer to the sea).” The problem asks us to find the total number of buildings that satisfy this condition.

Analysis

To determine whether a building \(i\) is visible from the sea, we need to know the maximum height \(M\) among buildings \(1\) through \(i-1\).

Naive Approach

For each building \(i\), if we search for the maximum value among \(H_1, \ldots, H_{i-1}\) every time, up to \(O(N)\) comparisons are needed per building. Since there are \(N\) buildings, the overall time complexity becomes \(O(N^2)\). Given the constraint \(N \leq 2 \times 10^5\) in this problem, an \(O(N^2)\) algorithm would require approximately \(4 \times 10^{10}\) operations, which would not finish within the time limit (TLE).

Efficient Approach

When examining buildings in order of their number (from closest to the sea), we can make efficient judgments by keeping track of the maximum height among all buildings seen so far. By maintaining the maximum height up to the previous building, we can determine whether the current building is visible in \(O(1)\) simply by comparing the new building’s height \(H_i\) with that maximum.

For example, consider buildings with heights \([12, 8, 10, 15]\): 1. Building 1 (height 12): The current maximum is 0, so \(12 > 0\) — visible. Update the maximum to 12. 2. Building 2 (height 8): \(8 \leq 12\), so not visible. The maximum remains 12. 3. Building 3 (height 10): \(10 \leq 12\), so not visible. The maximum remains 12. 4. Building 4 (height 15): \(15 > 12\), so visible. Update the maximum to 15.

In this way, the answer can be obtained by scanning the list just once.

Algorithm

1. Initialize a variable max_height to \(0\) to keep track of the current maximum height.
2. Initialize a variable count to \(0\) to count the number of buildings visible from the sea.
3. Examine the building heights \(H_1, H_2, \ldots, H_N\) in order:
   • If the current building’s height \(H_i\) is greater than max_height:
     • The building is visible, so increment count by 1.
     • Update max_height to \(H_i\).
4. Output the final value of count.

Complexity

• Time complexity: \(O(N)\)
  • Since we only scan the list of buildings once, the computation finishes in time proportional to the number of buildings \(N\).
• Space complexity: \(O(N)\)
  • If all input building heights are stored in a list, \(O(N)\) memory is used.

Implementation Notes

• Fast input: Since \(N\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() or similar methods.

• Initial value setting: Although the first building is always visible, by setting max_height = 0, the condition H_i > max_height is guaranteed to be true for the first building (since \(H_1 \geq 1\)), so it is handled correctly.

  Source Code

import sys

def main():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 建物の棟数
    n = int(input_data[0])
    # H: 各建物の高さのリスト
    h_list = list(map(int, input_data[1:]))
    
    count = 0
    max_height = 0
    
    # 各建物について、これまでの最大値と比較する
    for h in h_list:
        if h > max_height:
            count += 1
            max_height = h
            
    # 海から見える建物の個数を出力
    print(count)

if __name__ == "__main__":
    main()

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