Summary

This problem asks us to find the maximum length of a contiguous interval that is “mountain-shaped” and satisfies the condition “the difference between the maximum and minimum elevations is at least \(K\)”, given the elevation data of \(N\) mountains.

Analysis

1. Properties of “Mountain-shape” and Maximal Intervals

When an interval \([l, r]\) is mountain-shaped with a peak at \(k\) (\(l \leq k \leq r\)), the interval has the following characteristics: - The peak \(H_k\) is the maximum value in the interval. - Since the interval is monotonically increasing from the left end to the peak, the minimum value on the left side is the left end \(H_l\). - Since the interval is monotonically decreasing from the peak to the right end, the minimum value on the right side is the right end \(H_r\). - Therefore, the minimum value in the interval is \(\min(H_l, H_r)\).

Now, let’s fix a peak \(i\) and consider “how far we can extend the mountain shape to the left and right, centered at peak \(i\)”. - Left direction: As long as \(H_{j-1} < H_j\) holds, we can extend the left end. Let \(L[i]\) be the leftmost boundary of this extension. - Right direction: As long as \(H_j > H_{j+1}\) holds, we can extend the right end. Let \(R[i]\) be the rightmost boundary of this extension.

In this case, the interval \([L[i], R[i]]\) is the maximal mountain-shaped interval with peak \(i\).

2. Why checking only maximal intervals is sufficient

Consider any mountain-shaped interval \([l, r]\) (with peak \(k\)). This interval is always contained within the maximal interval \([L[k], R[k]]\) (i.e., \(L[k] \le l \le k \le r \le R[k]\)).

Comparing the maximal interval \([L[k], R[k]]\) with the original interval \([l, r]\): 1. Maximum value: Both are equal to the peak’s elevation \(H_k\). 2. Minimum value: Due to monotonicity, \(H_{L[k]} \le H_l\) and \(H_{R[k]} \le H_r\) hold, so the minimum value of the maximal interval is less than or equal to that of the original interval. 3. Elevation difference: Since the minimum value is smaller (or equal), the elevation difference (maximum - minimum) of the maximal interval is greater than or equal to that of the original interval. 4. Interval length: Naturally, the length of the maximal interval is greater than or equal to that of the original interval.

From this, if there exists an interval \([l, r]\) that satisfies the condition (elevation difference \(\ge K\)), the maximal interval \([L[k], R[k]]\) containing it must also satisfy the condition, and its length will be at least as large. Therefore, it is sufficient to check only the maximal intervals \([L[i], R[i]]\) for all \(i\) (\(1 \le i \le N\)).

3. Comparison with the naive approach

If we search all possible intervals \([l, r]\) naively, there are \(O(N^2)\) ways to choose the interval, and checking if each is mountain-shaped takes \(O(N)\) time, resulting in an overall time complexity of \(O(N^3)\) or \(O(N^2)\). With the constraint \(N \le 10^6\), this will result in a Time Limit Exceeded (TLE). However, with the “check only maximal intervals” approach described above, the intervals to check are narrowed down to \(N\) maximal intervals. By preprocessing, we can check each interval in \(O(1)\) time, allowing for a fast overall processing time of \(O(N)\).

---

Algorithm

We can use a method similar to dynamic programming (DP) to quickly calculate how far each element can be extended to the left and right.

Step 1: Calculating the left boundary \(L[i]\)

Scan from left to right (from \(i = 1\) to \(N-1\)): - If \(H_{i-1} < H_i\), the left side of peak \(i\) is directly connected to the left side of \(i-1\), so \(L[i] = L[i-1]\). - Otherwise, we cannot extend it further to the left, so \(L[i] = i\).

Step 2: Calculating the right boundary \(R[i]\)

Scan from right to left (from \(i = N-2\) to \(0\)): - If \(H_i > H_{i+1}\), the right side of peak \(i\) is directly connected to the right side of \(i+1\), so \(R[i] = R[i+1]\). - Otherwise, we cannot extend it further to the right, so \(R[i] = i\).

Step 3: Updating the maximum value

For each \(i\) (\(0 \le i < N\)), determine if the elevation difference of the maximal interval \([L[i], R[i]]\) is at least \(K\). Since the elevation difference can be represented as \(\max(H_i - H_{L[i]}, H_i - H_{R[i]})\), the condition is satisfied if either of the following holds: - \(H_i - H_{L[i]} \ge K\) - \(H_i - H_{R[i]} \ge K\)

If the condition is met, we update the maximum answer with the length of that interval, \(R[i] - L[i] + 1\).

---

Complexity

• Time Complexity: \(O(N)\) It takes \(O(N)\) to construct the array \(L\), \(O(N)\) to construct the array \(R\), and \(O(N)\) for the final check on each \(i\). Since it only runs a few loops of \(O(N)\) overall, it runs extremely fast.
• Space Complexity: \(O(N)\) We maintain the array \(H\) of size \(N\) to store the input elevations, and arrays \(L\) and \(R\) of size \(N\) to store the left and right boundary indices. Thus, the space complexity is \(O(N)\).

---

Implementation Points

• Pay attention to the direction of index traversal: When finding \(L[i]\), we use the previously calculated value \(L[i-1]\), so we loop from left to right (ascending order). Conversely, when finding \(R[i]\), we use the subsequently calculated value \(R[i+1]\), so we loop from right to left (descending order).

• Fast I/O: Since the input size is large (\(N \le 10^6\)), it is important to speed up standard I/O in C++ using cin.tie(NULL) and ios_base::sync_with_stdio(false).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }

    // L[i]: iから左に向かって狭義単調増加となる最小のインデックス
    vector<int> L(N);
    L[0] = 0;
    for (int i = 1; i < N; ++i) {
        if (H[i - 1] < H[i]) {
            L[i] = L[i - 1];
        } else {
            L[i] = i;
        }
    }

    // R[i]: iから右に向かって狭義単調減少となる最大のインデックス
    vector<int> R(N);
    R[N - 1] = N - 1;
    for (int i = N - 2; i >= 0; --i) {
        if (H[i] > H[i + 1]) {
            R[i] = R[i + 1];
        } else {
            R[i] = i;
        }
    }

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        // 頂点iを山頂とする山型の最大区間 [L[i], R[i]] において、
        // 最大値 H[i] と最小値 min(H[L[i]], H[R[i]]) の差が K 以上であるか判定
        if (H[i] - H[L[i]] >= K || H[i] - H[R[i]] >= K) {
            ans = max(ans, (long long)(R[i] - L[i] + 1));
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.