487B - Strip - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using str = string;
using T = tuple<ll, ll, ll>;

#define int long long
#define Base 31
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = a; i >= b; i --)
#define REP(i, n) for ( int i = 0 ; i < n ; ++i )
#define REPD(i, n) for ( int i =  n - 1 ; ~(--i) ; )
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

constexpr ll LINF = (1ll << 62);
constexpr int INF = (1ll << 30);
constexpr int MAX = 1e5 + 1;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "bai"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    // freopen(name".inp", "r", stdin);
    // freopen(name".ans", "w", stdout);
    cout << fixed << setprecision(10);
}
int n, s, l;
int a[MAX];

int f[MAX];

const int  Log = 18;
pii st[MAX][Log];
void Whisper(){
    cin >> n >> s >> l;
    FOR(i, 1, n) cin >> a[i];
    for (int i = 1 ; i <= n ; i++) st[i][0] = {a[i], a[i]};

    for (int k = 1 ; (1 << k) <= n ; k++){
        for (int i = 1; i + (1 << k) - 1 <= n; i++){
            st[i][k].fi = max(st[i][k - 1].fi, st[i + (1 << (k - 1))][k - 1].fi);
            st[i][k].se = min(st[i][k - 1].se, st[i + (1 << (k - 1))][k - 1].se);
        }
    }

    auto query_mx = [&](int l, int r){
        int k = Lg(r - l + 1);
        return max(st[l][k].fi, st[r - (1 << k) + 1][k].fi);
    };

    auto query_mn = [&](int l, int r){
        int k = Lg(r - l + 1);
        return min(st[l][k].se, st[r - (1 << k) + 1][k].se);
    };

    auto query = [&](int l, int r){
        return query_mx(l, r) - query_mn(l, r);
    };

    memset(f, 0x3f, sizeof f);

    //using f(i) as the minimum pieces till i
    int j = 0;
    f[0] = 0;

    for (int i = 1; i <= n; i++){
        while (i - j >= l && query(j + 1, i) > s || f[j] > INF) j++;
        if (i - j >= l) f[i] = min(f[i], f[j] + 1);
    }
    cout << (f[n] > INF ? -1 : f[n]);
}

signed main(){  
    setupIO();
    int Test = 1;
    // cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}