Problem p03033 (python)

Fixed submission:
#! /usr/bin/env python3
import bisect
import sys
sys.setrecursionlimit(10**9)



# Ref: https://qiita.com/takayg1/items/b7b3f7d458915bcc7a4e
class LazySegTree:
    def __init__(self, init_val, segfunc, ide_ele = 2**31 - 1):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [None] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])



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

    def update(self, l, r, x): # [l, r)
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = x
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r): # [l, r)
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res

    def gindex(self, l, r):
        l += self.num
        r += self.num
        lm = l >> (l & -l).bit_length()
        rm = r >> (r & -r).bit_length()

        while r > l:
            if l <= lm:
                yield l
            if r <= rm:
                yield r
            r >>= 1
            l >>= 1
        while l:
            yield l
            l >>= 1

def zarts(D,x): # 座標圧縮
    return bisect.bisect_left(D,x)
    

INF=10**20
def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    def segfunc(x,y):
        return min(x,y)

    v = [INF] * (Q+1)

    seg = LazySegTree(v,segfunc,ide_ele=INF)

    _X = list(enumerate(X))
    _X.sort(key=lambda x:x[1],reverse=True)
    for i,x in _X:
        l = zarts(D,S[i]-X[i])
        r = zarts(D,T[i]-X[i])
        
        if l == r: continue
        seg.update(l,r,X[i])
    

    for q in range(Q):
        d = q
        # print("d",d)
        x = seg.query(d,d+1)
        if x == INF:
            x = -1

        print(x)
    
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]"
    T = [int()] * (N)  # type: "List[int]"
    X = [int()] * (N)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, Q, S, T, X, D)



if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import numpy as np
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)


from numba import njit

@njit(cache=True)
def zarts(X,x): # 座標圧縮
    return np.searchsorted(X,x)

    
INF=10**18
def prepare(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    # heapq.heapify()
    count = 0
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        if pos_l == pos_r: continue
        # bisect.insort_left(L[pos_l],X[i])
        # bisect.insort_left(R[pos_r],X[i])

        L[pos_l][count] = X[i]
        R[pos_r][count] = X[i]
        count += 1

    # print(L[:count])

    return L,R


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        for i in range(len(rs)):
            x = int(rs[i])
            if x == INF: break
            
            if x in worked:
                worked.remove(x)
        
        for i in range(len(ls)):
            x = int(ls[i])
            if x == INF: break
            
            worked.add(x)

        if len(worked) == 0:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    T = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    X = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    D = np.array(D)

    L = np.full((Q+10,N+10),INF,dtype=np.int64)
    R = np.full((Q+10,N+10),INF,dtype=np.int64)
    L,R = prepare(N, Q, S, T, X, D, L,R)
    L = np.sort(L,1)
    R = np.sort(R,1)

    solve(N, Q, S, T, X, D,L,R)


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('zarts', '(i8[:],i8,)')(zarts)
    cc.export('prepare', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(prepare)
    cc.export('solve', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import zarts
        from my_module import prepare
        from my_module import solve

    except:
        cc_export()
        exit()

    main()

Buggy submission (verdict: Runtime Error):
import numpy as np
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)


from numba import njit

@njit(cache=True)
def zarts(X,x): # 座標圧縮
    return np.searchsorted(X,x)

    
INF=10**18
def prepare(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    L = np.full((Q+10,N+10),INF,dtype=np.int64)
    R = np.full((Q+10,N+10),INF,dtype=np.int64)
    # heapq.heapify()
    count = 0
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        if pos_l == pos_r: continue
        # bisect.insort_left(L[pos_l],X[i])
        # bisect.insort_left(R[pos_r],X[i])

        L[pos_l][count] = X[i]
        R[pos_r][count] = X[i]
        count += 1

    # print(L[:count])

    return L,R


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        for i in range(len(rs)):
            if rs[i] == INF: break
            x = int(rs[i])

            if x in worked:
                worked.remove(x)
        
        for i in range(len(ls)):
            if ls[i] == INF: break
            x = int(ls[i])
            worked.add(x)

        if not worked:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    T = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    X = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    D = np.array(D)


    L,R = prepare(N, Q, S, T, X, D)
    L = np.sort(L,1)
    R = np.sort(R,1)

    solve(N, Q, S, T, X, D,L,R)


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('zarts', '(i8[:],i8,)')(zarts)
    cc.export('prepare', '(i8,i8,i8[:],i8[:],i8[:],i8[:],)')(prepare)
    cc.export('solve', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import zarts
        from my_module import prepare
        from my_module import solve

    except:
        cc_export()
        exit()

    main()

Buggy submission (verdict: Runtime Error):
import numpy as np
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)


from numba import njit

@njit(cache=True)
def zarts(X,x): # 座標圧縮
    return np.searchsorted(X,x)

    
INF=10**18
def prepare(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    L = np.full((Q+10,N+10),INF,dtype=np.int64)
    R = np.full((Q+10,N+10),INF,dtype=np.int64)
    # heapq.heapify()
    count = 0
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        if pos_l == pos_r: continue
        # bisect.insort_left(L[pos_l],X[i])
        # bisect.insort_left(R[pos_r],X[i])

        L[pos_l][count] = X[i]
        R[pos_r][count] = X[i]
        count += 1

    # print(L[:count])

    return L,R


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        for i in range(len(rs)):
            if rs[i] == INF: break
            worked.remove(rs[i])
        
        for i in range(len(ls)):
            if ls[i] == INF: break
            worked.add(ls[i])

        if not worked:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    T = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    X = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    D = np.array(D)


    L,R = prepare(N, Q, S, T, X, D)
    L = np.sort(L,1)
    R = np.sort(R,1)

    solve(N, Q, S, T, X, D,L,R)


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('zarts', '(i8[:],i8,)')(zarts)
    cc.export('prepare', '(i8,i8,i8[:],i8[:],i8[:],i8[:],)')(prepare)
    cc.export('solve', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import zarts
        from my_module import prepare
        from my_module import solve

    except:
        cc_export()
        exit()

    main()

Buggy submission (verdict: Runtime Error):
import numpy as np
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)


from numba import njit

@njit(cache=True)
def zarts(X,x): # 座標圧縮
    return np.searchsorted(X,x)

    
INF=10**18
def prepare(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    L = np.full((Q,N),INF,dtype=np.int64)
    R = np.full((Q,N),INF,dtype=np.int64)
    # heapq.heapify()
    count = 0
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        if pos_l == pos_r: continue
        # bisect.insort_left(L[pos_l],X[i])
        # bisect.insort_left(R[pos_r],X[i])

        L[pos_l][count] = X[i]
        R[pos_r][count] = X[i]
        count += 1

    # print(L[:count])

    return L,R


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        for i in range(len(rs)):
            if rs[i] == INF: break
            worked.remove(rs[i])
        
        for i in range(len(ls)):
            if ls[i] == INF: break
            worked.add(ls[i])

        if not worked:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    T = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    X = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    D = np.array(D)


    L,R = prepare(N, Q, S, T, X, D)
    L = np.sort(L,1)
    R = np.sort(R,1)

    solve(N, Q, S, T, X, D,L,R)


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('zarts', '(i8[:],i8,)')(zarts)
    cc.export('prepare', '(i8,i8,i8[:],i8[:],i8[:],i8[:],)')(prepare)
    cc.export('solve', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import zarts
        from my_module import prepare
        from my_module import solve

    except:
        cc_export()
        exit()

    main()

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)

def zarts(X,x): # 座標圧縮
    return bisect.bisect_left(X,x)

    
INF=10**20
def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    pos = D.copy()
    L = collections.defaultdict(lambda: [])
    R = collections.defaultdict(lambda: [])

    # heapq.heapify()
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        bisect.insort_left(L[pos_l],X[i])
        bisect.insort_left(R[pos_r],X[i])
    

    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        while rs:
            worked.remove(rs.pop())
        
        while ls:
            worked.add(ls.pop())

        if not worked:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]"
    T = [int()] * (N)  # type: "List[int]"
    X = [int()] * (N)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, Q, S, T, X, D)



if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#! /usr/bin/env python3
#! /usr/bin/env python3
import bisect
import sys
sys.setrecursionlimit(10**9)



# Ref: https://qiita.com/takayg1/items/b7b3f7d458915bcc7a4e
class LazySegTree:
    def __init__(self, init_val, segfunc, ide_ele = 2**31 - 1):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [None] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])



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

    def update(self, l, r, x): # [l, r)
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = x
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r): # [l, r)
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res

    def gindex(self, l, r):
        l += self.num
        r += self.num
        lm = l >> (l & -l).bit_length()
        rm = r >> (r & -r).bit_length()

        while r > l:
            if l <= lm:
                yield l
            if r <= rm:
                yield r
            r >>= 1
            l >>= 1
        while l:
            yield l
            l >>= 1

def zarts(D,x): # 座標圧縮
    return bisect.bisect_left(D,x)
    

INF=10**20
def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    def segfunc(x,y):
        return min(x,y)

    v = [INF] * (len(D) + N + 1)

    seg = LazySegTree(v,segfunc,ide_ele=INF)

    _X = list(enumerate(X))
    _X.sort(key=lambda x:x[1],reverse=True)
    for i,x in _X:
        l = zarts(D,S[i]-X[i])
        r = zarts(D,T[i]-X[i])
        
        seg.update(l,r,X[i])
    

    for q in range(Q):
        d = q
        # print("d",d)
        x = seg.query(d,d+1)
        if x == INF:
            x = -1

        print(x)
    
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]"
    T = [int()] * (N)  # type: "List[int]"
    X = [int()] * (N)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, Q, S, T, X, D)



if __name__ == "__main__":
    main()