백준[baekjoon] 8201

#include<bits/stdc++.h>

using namespace std;

const int treeSize = 1<<22;
int t, n, lo, hi;
int minTree[treeSize*2], maxTree[treeSize*2];

bool query(int lo, int hi)
{
    int maxV = 0, minV = INT_MAX;
    for(int l = lo + treeSize, r = hi + treeSize; l<=r; l>>=1, r>>=1){
        if(l&1){ 
            maxV = max(maxV,maxTree[l]);
            minV = min(minV,minTree[l++]);
        }
        if(!(r&1)){
            maxV = max(maxV,maxTree[r]);
            minV = min(minV,minTree[r--]);
        } 
    }
    return (maxV - minV) <= t;
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> t >> n;
    fill(minTree, minTree + treeSize*2, INT_MAX);
    for(int i=0; i<n; i++){
        cin >> minTree[treeSize + i];
        maxTree[treeSize + i] = minTree[treeSize + i];
    }
    for(int i = treeSize-1; i>0; i--){
        minTree[i] = min(minTree[i<<1],minTree[i<<1|1]);
        maxTree[i] = max(maxTree[i<<1],maxTree[i<<1|1]);
    }
    int ans = 0;
    while(hi<n)
    {
        if(query(lo,hi)){
            hi++;
            ans = max(ans, hi-lo);
        }
        else lo++;
    }
    cout << ans << '\n';
    return 0;
}

twoPointer + segmentTree로 풀어보았다.