Overview

This problem asks us to find the maximum length of a contiguous interval \([l,r]\) that is “mountain-shaped” and where the difference between the maximum and minimum elevations in the interval is at least \(K\).

While extending the interval from the right end, we maintain the “longest mountain-shaped interval ending at the current right end \(r\)”.

Observation

We can think of the mountain-shaped condition in terms of the signs of the elevation differences between adjacent peaks.

• If \(H_i < H_{i+1}\), it is an “ascent”.
• If \(H_i > H_{i+1}\), it is a “descent”.
• If \(H_i = H_{i+1}\), it cannot form a mountain shape.

A mountain shape is a form where the elevation continues to increase for a while and then continues to decrease, like:

\[ 上り, 上り, \ldots, 上り, 下り, 下り, \ldots, 下り \]

In other words, there are two main reasons why an interval is not mountain-shaped:

1. It contains adjacent elements with equal elevations.
2. An “ascent” appears again after a “descent” has already occurred.

For example,

\[ 1, 3, 5, 4, 2 \]

is mountain-shaped, but

\[ 1, 3, 2, 4 \]

is not mountain-shaped because it goes “ascent \(\to\) descent \(\to\) ascent”.

---

Naively checking all intervals \([l,r]\) would result in \(O(N^2)\) intervals. Furthermore, checking the mountain-shaped condition and finding the maximum/minimum values for each interval would be far too slow for \(N \leq 10^6\).

Therefore, as we move the right end \(r\) from left to right, we efficiently maintain:

• The left end \(L\) of the longest mountain-shaped interval ending at the current \(r\).
• The maximum and minimum values within that interval.

---

The crucial point is that for a fixed right end \(r\), it is sufficient to consider only the longest mountain-shaped interval \([L,r]\).

If the difference between the maximum and minimum values in \([L,r]\) is at least \(K\), then this is the longest among the candidate intervals ending at the right end \(r\).

Conversely, if the difference in \([L,r]\) is less than \(K\), the difference between the maximum and minimum values in any shorter sub-interval contained within it cannot be any larger. Therefore, there are no valid candidate intervals ending at the right end \(r\).

Algorithm

We maintain the left end \(L\) as “the minimum position such that \([L,r]\) is mountain-shaped for the current right end \(r\)”.

Additionally, we keep track of where the most recent “descent” occurred as lastDown.

Updating the Left End \(L\) of the Mountain-Shaped Interval

When we advance the right end to \(r\), we compare it with the preceding elevation \(H_{r-1}\).

1. When \(H_{r-1} = H_r\)

An interval containing equal elevations cannot be mountain-shaped.

Therefore, the interval must start from \(r\).

We set:

\[ L = r \]

2. When \(H_{r-1} > H_r\)

This is a “descent”.

In a mountain shape, descents are allowed. However, since it will cause issues if an “ascent” appears later, we record the position of this descent.

We set:

\[ lastDown = r - 1 \]

3. When \(H_{r-1} < H_r\)

This is an “ascent”.

If there was a previous “descent”, it forms the following shape:

\[ 下り \to 上り \]

which is no longer mountain-shaped.

Therefore, we must exclude the last descent from our interval. If the last descent was at \(lastDown\), which means

\[ H_{lastDown} > H_{lastDown+1} \]

then to avoid including this descent, we must have

\[ L \geq lastDown + 1 \]

Therefore, we update:

\[ L = \max(L, lastDown + 1) \]

---

Managing the Maximum and Minimum Values

For each \(r\), we need to quickly find the maximum

\[ \max(H_L,\ldots,H_r) \]

and minimum

\[ \min(H_L,\ldots,H_r) \]

of the interval \([L,r]\).

This can be done using monotonic queues (deques).

• maxdq: A deque that manages candidates for the maximum value in the interval.
• mindq: A deque that manages candidates for the minimum value in the interval.

In maxdq, we store indices such that the corresponding elevations are in descending order. The front of the deque always represents the maximum value in the current interval.

In mindq, we store indices such that the corresponding elevations are in ascending order. The front of the deque always represents the minimum value in the current interval.

When adding the right end \(r\):

• In maxdq, we remove elements from the back that are less than or equal to \(H_r\).
• In mindq, we remove elements from the back that are greater than or equal to \(H_r\).

to maintain monotonicity.

Also, since any index to the left of \(L\) is outside the interval, we remove it from the front of the deques.

---

For each \(r\), we calculate:

\[ diff = \max(H_L,\ldots,H_r) - \min(H_L,\ldots,H_r) \]

and if

\[ diff \geq K \]

we update the answer with

\[ r - L + 1 \]

Complexity

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

Each index is added to and removed from a deque at most once, so the overall time complexity is linear.

Implementation Points

lastDown represents the position where the last descent occurred.

Since the code uses 0-indexed arrays, it is managed as follows:

if (H[r - 1] > H[r]) {
    lastDown = r - 1;
}

Also, if equal elevations appear, any interval containing that adjacent pair cannot be mountain-shaped, so we reset the interval by setting:

L = r;

In the deques managing the maximum and minimum values, we must always remove indices that are outside the interval after the left end \(L\) has advanced.

while (!maxdq.empty() && maxdq.front() < L) maxdq.pop_front();
while (!mindq.empty() && mindq.front() < L) mindq.pop_front();

This ensures that the front of the deques always represents the maximum and minimum values within the current interval \([L,r]\).

Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

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

    int L = 0;
    int lastDown = -1;
    int ans = 0;

    deque<int> maxdq, mindq;

    for (int r = 0; r < N; r++) {
        if (r > 0) {
            if (H[r - 1] == H[r]) {
                L = r;
            } else if (H[r - 1] > H[r]) {
                lastDown = r - 1;
            } else {
                L = max(L, lastDown + 1);
            }
        }

        while (!maxdq.empty() && H[maxdq.back()] <= H[r]) maxdq.pop_back();
        maxdq.push_back(r);

        while (!mindq.empty() && H[mindq.back()] >= H[r]) mindq.pop_back();
        mindq.push_back(r);

        while (!maxdq.empty() && maxdq.front() < L) maxdq.pop_front();
        while (!mindq.empty() && mindq.front() < L) mindq.pop_front();

        if (!maxdq.empty() && !mindq.empty()) {
            long long diff = H[maxdq.front()] - H[mindq.front()];
            if (diff >= K) {
                ans = max(ans, r - L + 1);
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.