Problem p02537 (python)

Fixed submission:
import sys

input = sys.stdin.buffer.readline


class SegmentTree:
    ele = 0
    func = max
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    # 1点更新
    def set(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    # 区間取得
    def query(self, left, right):
        # 開区間
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


n, k = map(int, input().split())
ans = 0
ST = SegmentTree(3000001)
for _ in range(n):
    val = int(input())
    lower = val - k
    lower = max(lower, 0)
    upper = val + k
    upper = min(upper, 3000000)
    temp = ST.query(lower, upper + 1) + 1
    ST.set(val, temp)
    ans = max(ans, temp)
print(ans)

Buggy submission (verdict: Runtime Error):
import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())

max_n = 300000 + 10
keta = max_n.bit_length()
num = 1 << (keta - 1)
SEG = [0] * (2 * num)

func = max
ele = 0


def update(idx, val):
    idx += num
    SEG[idx] = val
    for i in reversed(range(1, num)):
        SEG[i] = func(SEG[2 * i], SEG[2 * i + 1])


def query(left, right):
    res_left = ele
    res_right = ele
    left += num
    right += num
    while left < right:
        if left & 1:
            res_left = func(res_left, SEG[left])
            left += 1
        if right & 1:
            right -= 1
            res_right = func(SEG[right], res_right)
        left //= 2
        right //= 2
    return func(res_left, res_right)


ans = 0
for _ in range(n):
    val = int(input())
    lower = val - k
    upper = val + k
    if lower < 0:
        lower = 0
    if upper > num:
        upper = num
    temp = query(lower, upper + 1)
    update(val, temp + 1)
    ans = max(ans, temp + 1)

print(ans)

Buggy submission (verdict: Runtime Error):
import sys

input = sys.stdin.buffer.readline

n, k = map(int, input().split())

max_n = 300000 + 10
SEG = [0] * (2 * max_n)

func = max
ele = 0


def update(idx, val):
    idx += max_n
    SEG[idx] = val
    for i in reversed(range(1, max_n)):
        SEG[i] = func(SEG[2 * i], SEG[2 * i + 1])


def query(left, right):
    res_left = ele
    res_right = ele
    left += max_n
    right += max_n
    while left < right:
        if left & 1:
            res_left = func(res_left, SEG[left])
            left += 1
        if right & 1:
            right -= 1
            res_right = func(SEG[right], res_right)
        left //= 2
        right //= 2
    return func(res_left, res_right)


for _ in range(n):
    val = int(input())
    # print("range", max(0, val - k), min(max_n + 1, val + k + 1) - 1)
    lower = val - k
    upper = val + k
    if lower < 0:
        lower = 0
    if upper > max_n:
        upper = max_n
    temp = query(lower, upper + 1)
    update(val, temp + 1)


print(SEG[1])