Alitaulukot

#include <deque>
#include <iostream>
#include <vector>

template <class T, class Compare> struct MonotonicQueue {
    int l = 0, r = 0;
    std::deque<std::pair<T, int>> d;

    void push(T x) {
        while (!d.empty() && !Compare{}(d.back().first, x))
            d.pop_back();
        d.push_back({x, r++});
    }

    void pop() {
        if (d.front().second == l++)
            d.pop_front();
    }

    T get() {
        return d.front().first;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k;
    std::cin >> n >> k;
    std::vector<int> v(n);
    for (auto &x : v)
        std::cin >> x;
    MonotonicQueue<int, std::less<>> minq;
    MonotonicQueue<int, std::greater<>> maxq;
    long r = 0;
    for (int i = 0, j = -1; i < n; ++i) {
        maxq.push(v[i]);
        minq.push(v[i]);
        while (maxq.get() - minq.get() > k) {
            maxq.pop();
            minq.pop();
            j++;
        }
        r += i - j;
    }
    std::cout << r << '\n';
}

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