Alitaulukot

def bisect_desc(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] > x: lo = mid+1
        else: hi = mid
    return lo

def bisect_asc(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

class Ylitaulukko:
    def __init__(self, start, end):
        self.start = start
        self.end = end

def muodostaYlitaulukot(gayArray, n, k):
    tPointer = 0
    ePointer = 1
    lastEPointer = -1

    curMaxI = 0
    curMinI = 0
    maxPosses = [0]
    minPosses = [0]
    maxVals = [gayArray[0]]
    minVals = [gayArray[0]]
    lastMaxI = 0
    lastMinI = 0

    ylitaulukot = []

    while ePointer < n:
        while (ePointer < n) and (gayArray[ePointer] <= minVals[curMinI] + k) and (gayArray[ePointer] >= maxVals[curMaxI] - k):
            # max min val huolto
            ii = bisect_asc(minVals, gayArray[ePointer])
            lastMinI = ii
            curMinI = min(curMinI, ii)
            if ii == len(minVals):
                minVals.append(gayArray[ePointer])
                minPosses.append(ePointer)
            else:
                minVals[ii] = gayArray[ePointer]
                minPosses[ii] = ePointer

            ii = bisect_desc(maxVals, gayArray[ePointer])
            lastMaxI = ii
            curMaxI = min(curMaxI, ii)
            if ii == len(maxVals):
                maxVals.append(gayArray[ePointer])
                maxPosses.append(ePointer)
            else:
                maxVals[ii] = gayArray[ePointer]
                maxPosses[ii] = ePointer

            ePointer += 1

        # ePointer ei olisi enää laillinen lisäys
        if ePointer != lastEPointer:
            ylitaulukot.append(Ylitaulukko(tPointer, ePointer - 1))
            lastEPointer = ePointer

        #tPointer seuraavaan max/min +1 valueen, poista tämä value. Jos ei ole valueita niin +1
        if (maxPosses[curMaxI] == minPosses[curMinI]):
            tPointer = maxPosses[curMaxI] +1
            if tPointer < n:
                if curMaxI != lastMaxI or curMinI != lastMinI:
                    raise Exception("i cant believe youve done this")

                curMaxI = 0
                curMinI = 0
                maxPosses = [tPointer]
                minPosses = [tPointer]
                maxVals = [gayArray[tPointer]]
                minVals = [gayArray[tPointer]]
                lastMaxI = 0
                lastMinI = 0
        elif (maxPosses[curMaxI] < minPosses[curMinI]): # TOIMII
            tPointer = maxPosses[curMaxI] +1
            curMaxI += 1
        else:
            tPointer = minPosses[curMinI] +1    # TOIMII
            curMinI += 1

        ePointer = max(ePointer, tPointer + 1)  # TOIMII

    if ylitaulukot[-1].end != n-1:
        ylitaulukot.append(Ylitaulukko(n-1, n-1))

    return ylitaulukot  # TOIMII



def laskeAlitaulukot(ylitaulukot):
    result = 0
    lastEnd = -1
    for ylitaulukko in ylitaulukot:
        length = ylitaulukko.end - ylitaulukko.start + 1
        result += (length*(length+1))/2

        if lastEnd >= ylitaulukko.start:
            length = lastEnd - ylitaulukko.start + 1
            result -= (length*(length+1))/2

        lastEnd = ylitaulukko.end

    return result   # TOIMII

def main():
    n, k = [int(i) for i in input().split(" ")]
    gayArray = [int(i) for i in input().split(" ")]
    if n == 1:
        print("1")
    else:
        print(int(laskeAlitaulukot(muodostaYlitaulukot(gayArray, n, k))))   # TOIMII

main()  # TOIMII

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: WRONG ANSWER

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: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED