Problem p02537 (python)

Fixed submission:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write('\n'.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')


def construct_sum(segtree,a,n,func=max):
    for i in range(n):
        segtree[n + i] = a[i]
    for i in range(n - 1, 0, -1):
        segtree[i] = func(segtree[2 * i], segtree[2 * i + 1])

def update(pos, x, func=max):
    pos += n-1
    segtree[pos] = x
    while (pos>1):
        pos>>=1
        segtree[pos] = func(segtree[2 * pos], segtree[2 * pos + 1])

def get(l, r, func=max):
    l += n-1
    r += n-1
    s = 0
    while (l <= r):
        if l & 1:
            s = func(segtree[l],s)
            l+=1
        if (r+1) & 1:
            s = func(segtree[r],s)
            r-=1
        l >>= 1
        r >>= 1
    return s

n,k=mdata()
a=[int(data()) for i in range(n)]
n=max(a)+1
segtree = [0]*(2*n)
construct_sum(segtree,[0]*n,n)
ans=0
for i in a:
    a1=get(max(i-k+1,1),min(i+k+1,n))+1
    update(i+1,a1)
    ans=max(ans,a1)
out(ans)

Buggy submission (verdict: Runtime Error):
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write('\n'.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')

class LazySegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the lazy segment tree with data"""
        self._default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        self._lazy[2 * idx] = max(q,self._lazy[2 * idx])
        self._lazy[2 * idx + 1] = max(q,self._lazy[2 * idx+1])
        self.data[2 * idx] = max(q,self.data[2 * idx])
        self.data[2 * idx + 1] = max(q,self.data[2 * idx])

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1],self._lazy[idx])
            idx >>= 1

    def add(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start <= stop:
            if start & 1:
                self._lazy[start] = max(value,self._lazy[start])
                self.data[start] = max(value,self.data[start])
                start += 1
            if (stop+1) & 1:
                self._lazy[stop] = max(value, self._lazy[start])
                self.data[stop] = max(value, self.data[start])
                stop-=1
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy)

    def query(self, start, stop, default=0):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        # Apply all the lazily stored queries
        self._update(start)
        self._update(stop)

        res = default
        while start <= stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if (stop+1) & 1:

                res = self._func(res, self.data[stop])
                stop -= 1
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)




n,k=mdata()
a=[int(data()) for i in range(n)]
S=LazySegmentTree([0]*(max(a)+1))
ans=0
for i in a:
    a1=S.query(i-1,i-1)
    S.add(i-k-2,i+k-1,a1+1)
    ans = max(ans, a1)
    s1=[]
ans=max(ans,S.query(a[-1]-1,a[-1]-1))
out(ans)