Proficient.
Put your skills to the test.

Problem summary

Buildings of distinct positive heights stand from west to east. Insert a tower of height H in any gap, including the ends. A building receives its westward broadcast exactly when it is west of the tower, lower than H, and no taller building stands between it and the tower. Maximize the number of receivers.

Constraints

1≤N≤1000000; all heights≤10^9.

Worked example

Original statement sample.

12 180
200 170 130 90 150 140 40 30 100 160 50 110

5

Solution analysis

1. Consider placing the tower after each processed prefix. Looking left from that gap, receivers are the right-to-left record heights, stopping at the first building taller than H. Keep precisely these candidates in decreasing height order.
2. When a new building shorter than H arrives, it hides every lower candidate to its west; pop those candidates, then push the new height. If the new building exceeds H, it blocks every earlier receiver, so clear the stack. The stack size is the receiver count at this gap.
3. In the sample, after the first eight buildings the visible lower heights are170,150,140,40,30. There are five, and the next height100 hides40 and30. Comparing all prefix stack sizes finds the optimal position without separately scanning every prefix.

Why it works

Inductively the stack lists exactly the lower-than-H suffix maxima of the current prefix after its last above-H building. A new low building removes precisely those smaller candidates it blocks; a high building blocks every previous candidate. Thus each stack size is correct, and maximizing over every possible gap gives the optimum.

Watch out. Only buildings west of the tower count. A building taller than H is not a receiver, but still blocks earlier buildings. This is not the ordinary count of all buildings lower than H.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,towerHeight;
    cin>>n>>towerHeight;
    vector<int>visible;
    int answer=0;
    for(int i=0;i<n;i++){
        int height;
        cin>>height;
        if(height>towerHeight){
            visible.clear();
            continue;
        }
        while(!visible.empty()&&visible.back()<height){
            visible.pop_back();
        }
        // The new building hides all shorter candidates to its west.
        visible.push_back(height);
        answer=max(answer,static_cast<int>(visible.size()));
    }
    cout<<answer<<'\n';
}