Overview

This problem asks us to look at mountains in order from the front, where only mountains with elevation higher than the maximum elevation seen so far are “visible.” It can be solved with a single scan while updating the maximum value.

Analysis

Understanding the Problem

Let’s organize the conditions for a mountain to be “visible.”

• 1st mountain: Always visible since there are no mountains in front
• 2nd mountain and beyond: Visible only if its elevation is higher than all mountains in front of it

For example, if the mountain elevations are [3, 5, 2, 6, 4]: - Mountain 1 (elevation 3): Visible (first mountain) - Mountain 2 (elevation 5): Visible (higher than 3) - Mountain 3 (elevation 2): Not visible (5 or less, so hidden by mountain 2) - Mountain 4 (elevation 6): Visible (higher than any of 3, 5, 2) - Mountain 5 (elevation 4): Not visible (6 or less, so hidden by mountain 4)

The answer is 1 2 4.

Key Insight

The condition “higher than all mountains in front” can be rephrased as “higher than the maximum elevation among the mountains in front.”

This means we don’t need to compare each mountain with all previous mountains—we only need to keep track of the maximum value.

Problem with the Naive Approach

If we compare each mountain with all mountains before it: - Mountain 2 is compared with mountain 1 (1 comparison) - Mountain 3 is compared with mountains 1, 2 (2 comparisons) - … - Mountain N is compared with mountains 1 through N-1 (N-1 comparisons)

This requires a total of \(1 + 2 + \cdots + (N-1) = \frac{N(N-1)}{2}\) comparisons, which takes \(O(N^2)\) time. This won’t be fast enough for \(N = 2 \times 10^5\).

Solution

By managing “the maximum elevation so far” with a single variable, we can determine each mountain’s visibility in constant time.

Algorithm

1. Initialize variable max_height to 0 (to record the maximum elevation so far)
2. Look at mountains in order from the front (\(i = 1, 2, \ldots, N\))
3. For each mountain:
   • If \(i = 1\) (the first mountain), it’s always visible, so add it to the answer
   • If \(i \geq 2\), add it to the answer when \(H_i > \) max_height
   • Update max_height to \(\max(\)max_height\(, H_i)\)
4. Output the mountain numbers that were added to the answer

Complexity

• Time complexity: \(O(N)\)
  • We look at each mountain once and perform constant-time operations
• Space complexity: \(O(N)\)
  • Used for the array storing mountain elevations and the array storing the answer

Implementation Notes

• 0-indexed to 1-indexed conversion: Python arrays start from 0, but the output should be mountain numbers starting from 1, so output i + 1

• Handling the first mountain: Although we handle the first mountain specially with the condition i == 0, since max_height = 0 and \(H_i \geq 1\), the first mountain would actually always be judged as visible with just the condition H[i] > max_height (we write it explicitly for code readability)

• print(*visible): A convenient way to output list elements separated by spaces

  Source Code

N = int(input())
H = list(map(int, input().split()))

visible = []
max_height = 0

for i in range(N):
    if i == 0 or H[i] > max_height:
        visible.append(i + 1)
    max_height = max(max_height, H[i])

print(*visible)

---

This editorial was generated by claude4.5opus.