Alitaulukot

#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <bits/stdc++.h> 
#define lint long long int
 
using namespace std;
 
lint length(lint x)
{
	return x * (x + 1) / 2;
}
 
lint CalculateSubArray(lint arr[], lint n, lint k)
{
	lint len = 1;
	lint result = 0;
	lint duplicate_len = 0;
	
	lint max = arr[0];
	lint min = arr[0];
	
	lint max_index = 0;
	lint min_index = 0;
	
	lint breaker_index = 0;
	
	//An adventurer will always progress or get to the same point.
	for(lint i = 1; i < n; i++)
	{
		bool barrier_number = abs(arr[i] - arr[i - 1]) > k;
		bool MaxChange = max < arr[i];
		bool MinChange = min > arr[i];
		
		if(MaxChange) {
			max = arr[i];
			max_index = i;
		}
		if(MinChange) {
			min = arr[i];
			min_index = i;
		}
		if(max - min <= k) {
			len++;
		}
		else
		{
			result += length(len);
			if(barrier_number)
			{
				len = 1;
				max = arr[i];
				max_index = i;
				min = arr[i];
				min_index = i;
			}
			else
			{
				breaker_index = MaxChange * min_index + MinChange * max_index;
				lint range_1 = breaker_index + 1;
				lint range_2 = i-1;
				
				lint min2 = range_2; 
				lint max2 = range_2;
				//Within this range find the maximum or minimum index;
				for(lint b = range_2; b >= range_1; b--)
				{
					if(abs(arr[b] - arr[i]) > k) {
						break;
					}
					if(arr[b] < arr[min2])
					{
						min2 = b;
					}
					else if(arr[b] > arr[max2]) 
					{
						max2 = b;
					}	
				}
				lint desired_index = max2 * MinChange + min2 * MaxChange;
				len = i - desired_index + 1;
				duplicate_len = len - 1;
				
				max = arr[max2] * MinChange + arr[i] * MaxChange;
				max_index = max2  * MinChange + i * MaxChange;
				min = arr[min2]  * MaxChange + arr[i] * MinChange;
				min_index = min2  * MaxChange + i * MinChange;
			}
			
			result -= length(duplicate_len);
			duplicate_len = 0;
		}	
	}
	result += length(len);
	return result;
}
 
int main()
{
	lint n;
	cin >> n;
	lint k;
	cin >> k;
	lint arr[n];
	
	for(lint i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	cout << CalculateSubArray(arr, n, k);
	return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: WRONG ANSWER

Test 8

Group: 2, 3

Verdict: WRONG ANSWER

Test 9

Group: 2, 3

Verdict: WRONG ANSWER

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED