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