Overview

For a row of building blocks, we repeatedly perform an operation where a block is removed if its right neighbor is taller than itself, until no more blocks can be removed. The problem asks us to find the number of blocks that remain in the end.

Analysis

If we simulate the process directly as described in the problem statement, it will take \(O(N)\) time per round, and the number of rounds can be up to \(O(N)\) in the worst case. This results in an \(O(N^2)\) time complexity, which will lead to a TLE (Time Limit Exceeded) given the constraint \(N \leq 10^6\). Therefore, we need to find the rule that determines which blocks will ultimately remain.

A block \(A\) is removed when a block \(B\) that is taller than \(A\) appears to its immediate right. Even if the immediate right neighbor changes several times, eventually, the tallest block among those to the right of \(A\) will arrive to the immediate right of \(A\) and eliminate it.

In other words, for block \(A\) to survive until the end, it must have a height that is greater than or equal to the maximum height of all blocks to its right. Conversely, if we look at the blocks from right to left, only the blocks that update the “maximum height seen so far” (i.e., blocks that are monotonically non-decreasing when viewed from the right) will ultimately remain.

For example, if the heights are [2, 5, 3, 1, 4], looking from the right gives 4, 1, 3, 5, 2. - The first element 4 serves as the initial base and remains (maximum: 4). - 1 is less than the maximum of 4, so it is removed. - 3 is also less than the maximum of 4, so it is removed. - 5 is greater than or equal to the maximum of 4, so it remains (new maximum: 5). - 2 is less than the maximum of 5, so it is removed. Only 4 and 5 remain, which matches the actual simulation result.

Algorithm

1. Examine the blocks in order from the right end (\(N\)-th) to the left end (1st).
2. Keep track of the maximum height of the blocks seen so far, max_h (initialized to a value smaller than any possible block height, e.g., -1).
3. If the height \(h\) of the current block is greater than or equal to max_h, this block will survive until the end. Thus, we increment our count by \(1\) and update max_h with \(h\).
4. Once we have examined all the blocks up to the left end, the counted value is the answer.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\) (due to reading the input all at once. It can be reduced to \(O(1)\) if we read the elements one by one)

Implementation Points

• Since \(N \leq 10^6\) is large, using Python’s standard input() might lead to a TLE. Instead, you can use sys.stdin.buffer.read().split() to read the input all at once at high speed, thereby reducing the execution time.

• Since we traverse from right to left, we run the loop decrementing the array index from \(N\) towards \(1\).

  Source Code

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    count = 0
    max_h = -1
    for i in range(N, 0, -1):
        h = int(data[i])
        if h >= max_h:
            count += 1
            max_h = h
    print(count)

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.