Alitaulukot

#include <iostream>
 
using namespace std;
using ll=long long;
 
ll N = 1;
ll t[101010], l[303030], s[303030];
 
void setl(ll k, ll x) {
	k += N;
	for (k /= 2; k > 0; k /= 2) 
		l[k] = max(l[2*k], l[2*k+1]);
}
 
ll getl(ll a, ll b) {
	a += N;
	b += N;
	ll m = 0;
	while (a <= b) {
		if (a % 2 == 1) m = max(m, l[a++]);
		if (b % 2 == 0) m = max(m, l[b--]);
		a /= 2;
		b /= 2;
	}
	return m;
}
 
void sets(ll k, ll x) {
	k += N;
	for (k /= 2; k > 0; k /= 2) 
		s[k] = min(s[2*k], s[2*k+1]);
}
 
ll gets(ll a, ll b) {
	a += N;
	b += N;
	ll m = 1e9+1;
	while (a <= b) {
		if (a % 2 == 1) m = min(m, s[a++]);
		if (b % 2 == 0) m = min(m, s[b--]);
		a /= 2;
		b /= 2;
	}
	return m;
}
 
ll dif(ll a, ll b) {
	return getl(a, b) - gets(a, b);
}
 
int main() {
	ll n, k, v = 0;
	cin >> n >> k;
	while (N < n) N *= 2;
	for (ll i = 0; i < 2*N; i++) s[i] = 1e9+1;
	for (ll i = 0; i < n; i++) {
		cin >> t[i];
		l[N+i] = t[i];
		s[N+i] = t[i];
	}
	for (ll i = 0; i < N; i++) {
		setl(i, t[i]);
		sets(i, t[i]);
	}
	for (ll i = 0, j = 0; i < n; i++) {
		if (i > j) j = i;
		while (dif(i, j) <= k && j < n) {
			v += ++j-i;
		}
	}
	cout << v << endl;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED