Problem p03033 (python)

Fixed submission:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが小さい順に工事区間を見て，引っかかるならば区間更新．
    一度値を決定した場所は飛ばしながら更新するようにすればO(Q)
    nxtを入れながら進めば各ノードを2回しか見ないからO(Q)
    事前のソートで NlogN
    """

    
    N,Q=MI()
    xst2=[]#x,ごとに，Dがどの範囲なら引っかかるか(s~t)
    xi=[[0,0]for _ in range(N)]
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
        xi[i]=[x,i]
    xi.sort()
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
    inf=10**10
    ans=[inf]*(Q+4)#すこし多めにとっておく
    nxt=[0]*(Q+4)#次に見るべき番号
    for i in range(Q+4):
        nxt[i]=i+1
        
    """
    print(xi)
    print(xst2)"""
    
    
    for i in range(N):
        ii=xi[i][1]
        xx=xst2[ii][0]
        
        #0-index
        ss=bisect.bisect_left(D,xst2[ii][1])
        tt=bisect.bisect_left(D,xst2[ii][2])
        j=ss
        while j<tt:
            if ans[j]==inf:
                ans[j]=xx
            jj=j
            j=nxt[j]
            nxt[jj]=tt#次ここにきたら，ttのところまで移動するようにしておく
        """print(ii,xst2[ii][1],xst2[ii][2],xx,ss,tt)
        print(ans)
        print(nxt)"""

    
        
    for i in range(Q):
        res=ans[i]
        if res==inf:
            print(-1)
        else:
            print(res)
            
        
    
        

main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが大きい順に工事区間を見て，引っかかるならば区間更新
    """

    
    N,Q=MI()
    xst2=[]#x,ごとに，Dがどの範囲なら引っかかるか(s~t)
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
    xst2.sort(reverse=True)
    
    
    #遅延セグ木##
    INF=10**10
    LV = Q.bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)

    def gindex(l, r):
        L = l + N0; R = r + N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
            lazy[i-1] = None

    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = x
            if L & 1:
                lazy[L-1] = data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = min(data[2*i-1], data[2*i])

    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])
            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    ###
    
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
        

    #1~10**9は大きいので，Dに与えられた値のみを見る，
    
    for i in range(N):
        x,s,t=xst2[i][0],xst2[i][1],xst2[i][2]
        nums=bisect.bisect_left(D,s)
        numt=bisect.bisect_left(D,t)
        update(nums,numt,x)
        
    for i in range(Q):
        ans=query(i,i+1)
        if ans==INF:
            print(-1)
        else:
            print(ans)
        
    
        

main()