Overview

This problem asks us to find the maximum length of a contiguous interval of mountain peaks lined up from east to west that is “mountain-shaped” (strictly monotonically increasing on the left, strictly monotonically decreasing on the right) and where the difference between the maximum and minimum elevations is at least \(K\).

Analysis

Focus on the “Peak” of the Mountain-Shaped Interval

In a mountain-shaped interval \([l, r]\), there always exists a peak \(k\) which is the highest point, and it takes the form:

\[H_l < \cdots < H_k > \cdots > H_r\]

Thus, we can consider the question: “If we fix the peak at \(k\), what is the longest possible mountain-shaped interval?”

To make the mountain-shaped interval with peak \(k\) as long as possible, we should extend it to the left “as long as it strictly monotonically increases” and to the right “as long as it strictly monotonically decreases.” - Left end: We can extend to the left as long as \(H_{i} > H_{i-1}\) holds. - Right end: We can extend to the right as long as \(H_{i} > H_{i+1}\) holds.

If we precompute this for each \(k\), we can find the longest mountain-shaped interval for each peak in \(O(1)\) time.

Considering the Elevation Difference Condition

For the longest interval \([L, R]\) with a fixed peak \(k\): - The maximum value is always the peak \(H_k\). - The minimum value is the lower of the two endpoints, \(\min(H_L, H_R)\) (since the ends of the increasing/decreasing sequences are the lowest).

Therefore, the elevation difference is \(H_k - \min(H_L, H_R)\).

Why We Don’t Need to Consider Sub-intervals

Is it possible that “the longest interval does not satisfy the condition, but a shorter sub-interval does”? If we shrink the interval, the maximum value remains unchanged (the peak is still included), and the minimum value can only increase. Thus, the elevation difference can only decrease. In other words, if the longest interval for peak \(k\) does not satisfy the condition, no sub-interval will satisfy it either. Furthermore, since the longest interval has the maximum length, it is sufficient to check only the longest interval for each peak.

Comparison with the Naive Approach

Checking all intervals naively takes \(O(N^2)\) time, which will not run in time for \(N \leq 10^6\). With the above observation, we can check each peak \(k\) in \(O(1)\) time, reducing the overall time complexity to \(O(N)\).

Algorithm

1. Precompute the increasing range to the left: Let incLeft[i] be the leftmost position such that the sequence is strictly monotonically increasing up to the right end \(i\).
   • If \(H_i > H_{i-1}\), then incLeft[i] = incLeft[i-1]; otherwise, incLeft[i] = i.
2. Precompute the decreasing range to the right: Let decRight[i] be the rightmost position such that the sequence is strictly monotonically decreasing starting from the left end \(i\).
   • If \(H_i > H_{i+1}\), then decRight[i] = decRight[i+1]; otherwise, decRight[i] = i.
3. Iterate through all peaks \(k\):
   • Let \(L = \) incLeft[k] and \(R = \) decRight[k]. Then, \([L, R]\) is the longest mountain-shaped interval with peak \(k\).
   • If \(H_k - \min(H_L, H_R) \geq K\), update the answer with the length \(R - L + 1\).

Concrete Example

For \(H = [1, 3, 5, 2, 4]\) and \(K = 3\), let’s focus on the peak \(k=2\) (elevation \(5\)): - To the left, it extends as \(1 < 3 < 5\), so \(L = 0\). - To the right, it stops at \(5 > 2\), so \(R = 3\) (it does not extend further because \(2 < 4\)).

The interval \([0, 3] = (1, 3, 5, 2)\) is mountain-shaped. Its maximum is \(5\) and minimum is \(1\). Since the difference \(4 \geq 3\) is satisfied, the length \(4\) becomes a candidate for the answer.

Complexity

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

Implementation Details

• In the calculation of the elevation difference \(H_k - \min(H_L, H_R)\), it is sufficient to look at only the two endpoints for the minimum value (since it is mountain-shaped, all internal points are greater than or equal to the endpoints).

• Since \(N\) can be as large as \(10^6\), it is recommended to use fast I/O methods like scanf.

• The interval lengths and elevation differences can exceed \(10^9\), so use long long to prevent overflow.

• An interval with only one peak (length 1) has an elevation difference of \(0\). Since \(K \geq 1\), it will not satisfy the condition. Therefore, if there are no valid candidates, the answer naturally becomes \(0\).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N; long long K;
    {
        // fast input
    }
    scanf("%d %lld", &N, &K);
    vector<long long> H(N);
    for(int i=0;i<N;i++) scanf("%lld", &H[i]);
    
    vector<int> incLeft(N), decRight(N);
    for(int i=0;i<N;i++){
        if(i>0 && H[i]>H[i-1]) incLeft[i]=incLeft[i-1];
        else incLeft[i]=i;
    }
    for(int i=N-1;i>=0;i--){
        if(i<N-1 && H[i]>H[i+1]) decRight[i]=decRight[i+1];
        else decRight[i]=i;
    }
    
    long long ans=0;
    for(int k=0;k<N;k++){
        int L=incLeft[k];
        int R=decRight[k];
        long long mn = min(H[L], H[R]);
        if(H[k]-mn >= K){
            long long len = (long long)R - L + 1;
            if(len>ans) ans=len;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.