Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from collections import defaultdict


def update(heap, a, mode=1):
    while heap and abs(a - heap[0][0]) <= K:
        prev, length = heappop(heap)
        dp[a * mode] = max(dp[a * mode], length + 1)
    for key, value in dp.items():
        heappush(heap, (key * mode, value))


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
dp = defaultdict(int)
bigger = [(-A[0], -1)]
smaller = [(A[0], 1)]
for a in A[1:]:
    update(bigger, -a, -1)
    update(smaller, a)
print(max(dp.values()))

Fixed submission:
def update(i, v):
    i += length
    dp[i] = max(v, dp[i])
    while i:
        i //= 2
        dp[i] = max(dp[2 * i], dp[2 * i + 1])


def query(l, r):
    l += length
    r += length
    res = 0
    while l < r:
        if l % 2:
            res = max(dp[l], res)
            l += 1
        l //= 2
        if r % 2:
            res = max(dp[r - 1], res)
            r -= 1
        r //= 2
    return res


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
length = 1 << 20
dp = [0] * (2 * length)
res = 0
for a in A:
    cur = query(max(a - K, 0), min(a + K + 1, 300005))
    res = max(res, cur + 1)
    update(a, cur + 1)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
dp = defaultdict(int)
for a in A:
    for prev in list(dp.keys()):
        if abs(prev - a) <= K:
            dp[a] = max(dp[prev] + 1, dp[a])
    dp[a] = max(1, dp[a])
print(max(dp.values()))

Fixed submission:
def update(i, v):
    i += length
    dp[i] = max(v, dp[i])
    while i:
        i //= 2
        dp[i] = max(dp[2 * i], dp[2 * i + 1])


def query(l, r):
    l += length
    r += length
    res = 0
    while l < r:
        if l % 2:
            res = max(dp[l], res)
            l += 1
        l //= 2
        if r % 2:
            res = max(dp[r - 1], res)
            r -= 1
        r //= 2
    return res


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
length = 1 << 20
dp = [0] * (2 * length)
res = 0
for a in A:
    cur = query(max(a - K, 0), min(a + K + 1, 300005))
    res = max(res, cur + 1)
    update(a, cur + 1)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)


@lru_cache(None)
def dp(i, prev):
    if i == N:
        return 0
    else:
        if prev is None or abs(A[i] - prev) <= K:
            return max(dp(i + 1, prev), dp(i + 1, A[i]) + 1)
        else:
            return dp(i + 1, prev)

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
print(dp(0, None))


Fixed submission:
def update(i, v):
    i += length
    dp[i] = max(v, dp[i])
    while i:
        i //= 2
        dp[i] = max(dp[2 * i], dp[2 * i + 1])


def query(l, r):
    l += length
    r += length
    res = 0
    while l < r:
        if l % 2:
            res = max(dp[l], res)
            l += 1
        l //= 2
        if r % 2:
            res = max(dp[r - 1], res)
            r -= 1
        r //= 2
    return res


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
length = 1 << 20
dp = [0] * (2 * length)
res = 0
for a in A:
    cur = query(max(a - K, 0), min(a + K + 1, 300005))
    res = max(res, cur + 1)
    update(a, cur + 1)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)


@lru_cache(None)
def dp(i, prev):
    if i == N:
        return 0
    else:
        if prev is None or abs(A[i] - prev) <= K:
            return max(dp(i + 1, prev), dp(i + 1, A[i]) + 1)
        else:
            return dp(i + 1, prev)

N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
print(dp(0, None))

Fixed submission:
def update(i, v):
    i += length
    dp[i] = max(v, dp[i])
    while i:
        i //= 2
        dp[i] = max(dp[2 * i], dp[2 * i + 1])


def query(l, r):
    l += length
    r += length
    res = 0
    while l < r:
        if l % 2:
            res = max(dp[l], res)
            l += 1
        l //= 2
        if r % 2:
            res = max(dp[r - 1], res)
            r -= 1
        r //= 2
    return res


N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
length = 1 << 20
dp = [0] * (2 * length)
res = 0
for a in A:
    cur = query(max(a - K, 0), min(a + K + 1, 300005))
    res = max(res, cur + 1)
    update(a, cur + 1)
print(res)