Alitaulukot

#include <bits/stdc++.h>
#include <string.h>
#include <deque>
#include <algorithm>

using namespace std;

#define abs(x) (x < 0 ? -x : x)

int main(int argv, char *argc[]){
    int len, diff;
    cin >> len >> diff;

    int *numbers = new int[len];

    //int **nPointers = new int*[len]();

    for_each(numbers, numbers + len, [](auto &el){
        cin >> el;
    });

    long result = 0;

    int s = 0;
    int i = 0;


    int min, max, cur;

    int maxn, minn;

    len--;

emptyStart:
    cur = numbers[s];
    max = min = cur;
    maxn = minn = s;

    while(i < len){
        cur = numbers[++i];
        if(cur <= min){
            if(min - cur > diff){
                // None of the current substring fit...
                long n = i - s;
                result += (n*n + n) >> 1;
                s = i;
                goto emptyStart;
            }
            min = cur;
            minn = i;
            if(max - min > diff){
                // Search for all values after the maximum for a max that
                // fits...

                int omaxi = maxn;

                int n = i;
                maxn = i;
                max = cur;

                for(; n >= omaxi && numbers[n] - min <= diff; n--){
                    if(numbers[n] > max){
                        max = numbers[n];
                        maxn = n;
                    }
                }

                // All numbers from s to n are to be discarded
                long u = i - s;
                long l = u + s - n;

                result += (u + l) * (n + 1 - s) >> 1;

                s = n + 1;
            } 

        }else if(cur >= max){
            if(cur - max > diff){
                // None of the current substring fit...
                int n = i - s;
                result += (n*n + n) >> 1;
                s = i;
                goto emptyStart;
            }
            max = cur;
            maxn = i;
            if(max - min > diff){
                // Search for all values after the minimum for a max that
                // fits...

                int omini = minn;

                int n = i;
                minn = i;
                min = cur;

                for(; n >= omini && max - numbers[n] <= diff; n--){
                    if(numbers[n] < min){
                        min = numbers[n];
                        minn = n;
                    }
                }

                // All numbers from s to n are to be discarded
                //n++;

                long u = i - s;
                long l = u + s - n;

                result += (u + l) * (n + 1 - s) >> 1;

                //result += (i + n - 2*s)*(n-s) >> 1;

                s = n + 1;
            } 
        }
    }

    long n = i + 1 - s;
    result += (n*n + n) >> 1;

    cout << result;

    return EXIT_SUCCESS;
}

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: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED