Problem p03033 (python)

Fixed submission:
import sys
import bisect
from heapq import heappop, heappush, heapify
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

'''
import random
N = 2*10**5
Q = 2*10**5
STX = []
for i in range(N):
    S,T = sorted([random.randint(0,10**9-1) for i in range(2)])
    if S == T:
        T += 1
    X = random.randint(1,10**9)
    STX.append([S,T,X])
D = sorted([random.randint(0,10*9) for i in range(Q)])
'''

inf = 10**15
PFXS = [(s-x,True,x) for s,t,x in STX]
PFXT = [(t-x,False,x) for s,t,x in STX]
PFX = PFXS + PFXT
PFX.append((-inf,True,inf))
PFX.append((inf,False,inf))
PFX.sort()

addq = [inf]
delq = [inf+1]
iterD = iter(D)

d = next(iterD)
for p,f,x in PFX:
    while d < p:
        ans = addq[0] if not addq[0] == inf else -1
        print(ans)
        try:
            d = next(iterD)
        except:
            exit()
    if f:
        heappush(addq, x)
    else:
        heappush(delq, x)
    while addq[0] == delq[0]:
        heappop(addq)
        heappop(delq)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

'''
N,Q = 2*10**4,2*10**4
STX = []
order = 10**5
import random
for i in range(N):
    s = random.randint(0, order-1)
    t = random.randint(s+1,order)
    x = random.randint(1,order)
    STX.append([s,t,x])
D = sorted([random.randint(1,order) for i in range(Q)])

'''
inf = 10**12

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        self.lazy = [default] * (self.l * 2)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def update(self,k):
        if self.lazy[k] == self.default:
            return
        if k < self.l:
            self.lazy[2*k] = self.op(self.lazy[2*k], self.lazy[k])
            self.lazy[2*k+1] = self.op(self.lazy[2*k+1], self.lazy[k])
        self.data[k] = self.op(self.data[k],self.lazy[k])
        self.lazy[k] = self.default

    def set(self,i,j,val):
        def f(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return
            if i <= s and t <= j: # included
                self.lazy[k] = val
                self.update(k)
                return
            f(self,i,j,2*k,s,(s+t)//2)
            f(self,i,j,2*k+1,(s+t)//2,t)
            self.data[k] = self.op(self.data[2*k], self.data[2*k+1])
        return f(self,i,j,1,0,self.l)

    def get(self,i,j):
        def g(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return self.default # unit element
            if i <= s and t <= j: # has intersection
                return self.data[k]
            # left + right
            return self.op(g(self,i,j,2*k,s,(s+t)//2),g(self,i,j,2*k+1,(s+t)//2,t))
        return g(self,i,j,1,0,self.l)

def segsolve():
    import numpy as np
    sstx = sum([[s-x,t-x] for s,t,x in STX],[])
    sstx = sorted(set(sstx))
    comp = {s:i for i,s in enumerate(sstx)}

    d = np.searchsorted(sstx,D,side='left')

    seg = SegmentTree([inf] * len(sstx), min, inf)
    for s,t,x in STX:
        s = comp[s-x]
        t = comp[t-x]
        seg.set(s,t,x)

    for di in d:
        t = seg.get(di,di+1)
        if t == inf:
            t = -1
        print(t)

def answer():
    import bisect
    from collections import defaultdict,deque
    l = []
    for s,t,x in STX:
        l.append([s-x,True,x])
        l.append([t-x,False,x])
    l.sort()
    m = deque([])
    rm = defaultdict(int)

    i = 0
    for time,add,x in l:
        while i < Q and time > D[i]:
            while m:
                if rm[m[0]] == 0:
                    m.popleft()
                else:
                    print(m[0])
                    break
            else:
                print(-1)
            i += 1
        if add:
            bisect.insort(m,x)
            rm[x] = 1
        else:
            rm[x] = 0

    while i < Q:
        print(-1)
        i += 1

answer()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

'''
N,Q = 2*10**4,2*10**4
STX = []
order = 10**5
import random
for i in range(N):
    s = random.randint(0, order-1)
    t = random.randint(s+1,order)
    x = random.randint(1,order)
    STX.append([s,t,x])
D = sorted([random.randint(1,order) for i in range(Q)])

'''
inf = 10**12

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        self.lazy = [default] * (self.l * 2)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def update(self,k):
        if self.lazy[k] == self.default:
            return
        if k < self.l:
            self.lazy[2*k] = self.op(self.lazy[2*k], self.lazy[k])
            self.lazy[2*k+1] = self.op(self.lazy[2*k+1], self.lazy[k])
        self.data[k] = self.op(self.data[k],self.lazy[k])
        self.lazy[k] = self.default

    def set(self,i,j,val):
        def f(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return
            if i <= s and t <= j: # included
                self.lazy[k] = val
                self.update(k)
                return
            f(self,i,j,2*k,s,(s+t)//2)
            f(self,i,j,2*k+1,(s+t)//2,t)
            self.data[k] = self.op(self.data[2*k], self.data[2*k+1])
        return f(self,i,j,1,0,self.l)

    def get(self,i,j):
        def g(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return self.default # unit element
            if i <= s and t <= j: # has intersection
                return self.data[k]
            # left + right
            return self.op(g(self,i,j,2*k,s,(s+t)//2),g(self,i,j,2*k+1,(s+t)//2,t))
        return g(self,i,j,1,0,self.l)

def segsolve():
    import numpy as np
    sstx = sum([[s-x,t-x] for s,t,x in STX],[])
    sstx = sorted(set(sstx))
    comp = {s:i for i,s in enumerate(sstx)}

    d = np.searchsorted(sstx,D,side='left')

    seg = SegmentTree([inf] * len(sstx), min, inf)
    for s,t,x in STX:
        s = comp[s-x]
        t = comp[t-x]
        seg.set(s,t,x)

    for di in d:
        t = seg.get(di,di+1)
        if t == inf:
            t = -1
        print(t)

def answer():
    import bisect
    from collections import defaultdict,deque
    l = []
    for s,t,x in STX:
        l.append([s-x,True,x])
        l.append([t-x,False,x])
    l.sort()
    m = deque([])
    rm = defaultdict(int)

    i = 0
    for time,add,x in l:
        while i < Q and time > D[i]:
            while m:
                if rm[m[0]] == 0:
                    m.popleft()
                else:
                    print(m[0])
                    break
            else:
                print(-1)
            i += 1
        if add:
            bisect.insort(m,x)
            rm[x] = 1
        else:
            rm[x] = 0

    while i < Q:
        print(-1)
        i += 1

answer()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

'''
N,Q = 2*10**1,2*10**1
STX = []
order = 10**2
import random
for i in range(N):
    s = random.randint(0, order-1)
    t = random.randint(s+1,order)
    x = random.randint(1,order)
    STX.append([s,t,x])
D = sorted([random.randint(1,order) for i in range(Q)])
'''

inf = 10**12

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        self.lazy = [default] * (self.l * 2)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def update(self,k):
        if self.lazy[k] == self.default:
            return
        if k < self.l:
            self.lazy[2*k] = self.op(self.lazy[2*k], self.lazy[k])
            self.lazy[2*k+1] = self.op(self.lazy[2*k+1], self.lazy[k])
        self.data[k] = self.op(self.data[k],self.lazy[k])
        self.lazy[k] = self.default

    def set(self,i,j,val):
        def f(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return
            if i <= s and t <= j: # included
                self.lazy[k] = val
                self.update(k)
                return
            f(self,i,j,2*k,s,(s+t)//2)
            f(self,i,j,2*k+1,(s+t)//2,t)
            self.data[k] = self.op(self.data[2*k], self.data[2*k+1])
        return f(self,i,j,1,0,self.l)

    def get(self,i,j):
        def g(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return self.default # unit element
            if i <= s and t <= j: # has intersection
                return self.data[k]
            # left + right
            return self.op(g(self,i,j,2*k,s,(s+t)//2),g(self,i,j,2*k+1,(s+t)//2,t))
        return g(self,i,j,1,0,self.l)

def segsolve():
    import numpy as np
    sstx = sum([[s-x,t-x] for s,t,x in STX],[])
    sstx = sorted(set(sstx))
    comp = {s:i for i,s in enumerate(sstx)}

    d = np.searchsorted(sstx,D,side='left')

    seg = SegmentTree([inf] * len(sstx), min, inf)
    for s,t,x in STX:
        s = comp[s-x]
        t = comp[t-x]
        seg.set(s,t,x)

    for di in d:
        t = seg.get(di,di+1)
        if t == inf:
            t = -1
        print(t)

def answer():
    import bisect
    l = []
    for s,t,x in STX:
        l.append([s-x,True,x])
        l.append([t-x,False,x])
    l.sort()
    m = []
    i = 0
    for time,add,x in l:
        while time > D[i]:
            if m:
                print(m[0])
            else:
                print(-1)
            i += 1
        if add:
            bisect.insort(m,x)
        else:
            m.remove(x)
    while i < Q:
        print(-1)
        i += 1


answer()