Overview

This problem asks us to find the number of blocks that ultimately remain by scanning a sequence of blocks from right to left while keeping track of the maximum height of the blocks to their right.

Analysis

If we simulate the process exactly as described in the problem statement, we would traverse the sequence and remove blocks in each round. However, since \(N \leq 10^6\) is quite large, a naive simulation could take \(O(N^2)\) in the worst case, resulting in a TLE (Time Limit Exceeded). Therefore, we need to understand the core nature of the operations.

Looking at the operations in each round, the cursor moves from right to left. If the block at position \(k\) is taller than the block at position \(k-1\), the block at position \(k-1\) is removed. This can be viewed as an operation where “a taller block on the right crushes shorter blocks to its left.”

For a certain block \(A\) to ultimately remain, there must not be any block to the right of \(A\) that is taller than \(A\). If such a block exists, that taller block will eventually come from the right and crush \(A\).

Conversely, if \(A\) is taller than any block to its right, \(A\) will remain without being crushed by anyone. Furthermore, \(A\) has the potential to crush blocks to its left.

Therefore, we can see that the blocks that ultimately remain are only those that update (or equal) the maximum height encountered so far when scanned from right to left.

Let’s consider a concrete example with \(H = [3, 1, 4, 1, 5, 9, 2]\). We scan from the right end (2) to the left end (3): - 2: There is nothing to its right, so it remains. Update the maximum height to 2. - 9: Since it is greater than 2, it remains. Update the maximum height to 9. - 5: Since it is smaller than 9, the 9 will come from the right and crush it. It disappears. - 1: Since it is smaller than 9, it disappears. - 4: Since it is smaller than 9, it disappears. - 1: Since it is smaller than 9, it disappears. - 3: Since it is smaller than 9, it disappears.

As a result, only 9 and 2 remain, so the answer is 2.

Algorithm

Based on the above analysis, we can find the answer using the following algorithm: 1. Initialize a variable max_h to \(0\), which will store the maximum height of the blocks seen so far. Also, initialize the answer counter ans to \(0\). 2. Loop through the array \(H\) from the right end (index \(N-1\)) to the left end (index \(0\)). 3. If the height of the current block \(H[i]\) is greater than or equal to max_h, this block remains. Thus, increment ans by \(1\) and update max_h to \(H[i]\). 4. If \(H[i]\) is less than max_h, this block will be crushed, so do nothing. 5. After the loop ends, output ans.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Implementation Details

• Since \(N\) is very large (\(10^6\)), in C++, you should include ios_base::sync_with_stdio(false); cin.tie(NULL); to speed up input and output operations.

• Since the constraints guarantee that the height of each block is at least \(1\), initializing max_h to \(0\) works perfectly without any issues.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    int max_h = 0;
    int ans = 0;
    for (int i = N - 1; i >= 0; --i) {
        if (H[i] >= max_h) {
            ans++;
            max_h = H[i];
        }
    }
    cout << ans << "\n";
    return 0;
}

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