Problem p03033 (python)

Fixed submission:
import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(q, t)
        t = []
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()

Buggy submission (verdict: Runtime Error):
import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        t = []
        push(q, t)
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()

Buggy submission (verdict: Runtime Error):
import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(t)
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()

Buggy submission (verdict: Runtime Error):
#test
def hersCode(L, n):
  ok = len(L)
  ng = l
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  STX.sort(key = lambda x: x[2])

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)
    continue
    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Buggy submission (verdict: Runtime Error):
#test
def hersCode(L, n):
  ok = len(L)
  ng = l
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  STX.sort(key = lambda x: x[2])

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)
    continue()
    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Buggy submission (verdict: Runtime Error):
class RBT:
  B = 0
  R = 1

  class node:
    def __init__(s, x, col = 1):
      s.data = x
      s.col = col
      s.l = None
      s.r = None

  def __init__(s):
    s.root = None
    
  def insert(s, x):
    s.root, f = s.insert_sub(s.root, x)
    s.root.col = s.B

  def insert_sub(s, n, x):
    if n is None:
      return s.node(x), False
    if x < n.data:
      n.l, f = s.insert_sub(n.l, x)
      return s.check_left(n, f)
    else:
      n.r, f = s.insert_sub(n.r, x)
      return s.check_right(n, f)

  def check_left(s, n, f):
    if f:
      return n, f
    if n.col == s.B:
      f = True
      if n.l.r is not None and n.l.r.col == s.R:
        n.l = s.rot_left(n.l)
      if n.l.l is not None and n.l.l.col == s.R:
        if n.r is not None and n.r.col == s.R:
          s.split(n)
          f = False
        else:
          n = s.rot_right(n)
    return n, f

  def check_right(s, n, f):
    if f:
      return n, f
    if n.col == s.B:
      f = True
      if n.r.l is not None and n.r.l.col == s.R:
        n.r = s.rot_right(n.r)
      if n.r.r is not None and n.r.r.col == s.R:
        if n.l is not None and n.l.col == s.R:
          s.split(n)
          f = False
        else:
          n = s.rot_left(n)
    return n, f

  def rot_left(s, n):
    rn = n.r
    n.r = rn.l
    rn.l = n
    rn.col = n.col
    n.col = s.R
    return rn
  
  def rot_right(s, n):
    ln = n.l
    n.l = ln.r
    ln.r = n
    ln.col = n.col
    n.col = s.R
    return ln

  def split(s, n):
    n.col = s.R
    n.l.col = s.B
    n.r.col = s.B

  def check_col(s, n, col):
    return n is not None and n.col == col

  def keep_right(s, n, f):
    if f:
      return n, f
    if s.check_col(n.l.l, s.B) and s.check_col(n.l.r, s.B):
      if n.l.col == s.B:
        n.l.col = s.R
        if n.col == s.B:
          return n, False
        n.col = s.B
      else:
        n = s.lot_right(n)
        n.r, _ = s.keep_right(n.r, False)
    else:
      if s.check_col(n.l.r, s.R):
        n.l = s.rot_left(n.l)
      n = s.rot_right(n)
      if s.check_col(n.r, s.R):
        n.r.col = s.B
      if s.check_col(n.l, s.R):
        n.l.col = s.B
      return n, True

  def keep_left(s, n, f):
    if f:
      return n, f
    if s.check_col(n.r.l, s.B) and s.check_col(n.r.r, s.B):
      if n.r.col == s.B:
        n.r.col = s.R
        if n.col == s.B:
          return n, False
        n.col = s.B
      else:
        n = s.lot_left(n)
        n.l, _ = s.keep_left(n.l, False)
    else:
      if s.check_col(n.r.l, s.R):
        n.r = s.rot_right(n.r)
      n = s.rot_left(n)
      n.l.col = s.B
      n.r.col = s.B
      return n, True

  def isNone(s):
    return s.root == None

  def get_min(s):
    return s.get_min_sub(s.root)

  def get_min_sub(s, n):
    while n.l is not None:
      n = n.l
    return n.data

  def delete(s, x):
    s.root, f = s.delete_sub(s.root, x)

  def delete_sub(s, n, x):
    if n is None:
      return n, True
    if x == n.data:
      if n.l is None and n.r is None:
        return None, n.col == s.R
      elif n.r is None:
        n.l.col = s.B
        return n.l, True
      elif n.l is None:
        n.r.col = s.B
        return n.r, True
      else:
        n.data = s.get_min_sub(n.r)
        n.r, f = s.delete_sub(n.r, n.data)
        return s.keep_right(n, f)
    elif x < n.data:
      n.l, f = s.delete_sub(n.l, x)
      return s.keep_left(n, f)
    else:
      n.r, f = s.delete_sub(n.r, x)
      return s.keep_right(n, f)

  def print_node(s, n, x):
    color = ("B", "R")
    if n is not None:
      s.print_node(n.l, x + 1)
      print("   " * x, color[n.col], n.data)
      s.print_node(n.r, x + 1)

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  L = []
  for s, t, x in STX:
    L.append([s - x, x])
    L.append([t - x, -x])
  L.sort()

  rbt = RBT()

  dc = 0
  lc = 0
  while dc < len(D):
    if lc == len(L) or D[dc] < L[lc][0]:
      if rbt.isNone():
        t = -1
      else:
        t = rbt.get_min()
      while lc == len(L) or D[dc] < L[lc][0]:
        print(t)
        dc += 1
        if dc == len(D):
          break
    else:
      while D[dc] >= L[lc][0]:
        k = L[lc][1]
        if k < 0:
          rbt.delete(-k)
        else:
          rbt.insert(k)
        lc += 1
        if lc == len(L):
          break

main()

Buggy submission (verdict: Runtime Error):
class RBT:
  B = 0
  R = 1

  class node:
    def __init__(s, x, col = 1):
      s.data = x
      s.col = col
      s.l = None
      s.r = None

  def __init__(s):
    s.root = None
    
  def insert(s, x):
    s.root, f = s.insert_sub(s.root, x)
    s.root.col = s.B

  def insert_sub(s, n, x):
    if n is None:
      return s.node(x), False
    if x < n.data:
      n.l, f = s.insert_sub(n.l, x)
      return s.check_left(n, f)
    else:
      n.r, f = s.insert_sub(n.r, x)
      return s.check_right(n, f)

  def check_left(s, n, f):
    if f:
      return n, f
    if n.col == s.B:
      f = True
      if n.l.r is not None and n.l.r.col == s.R:
        n.l = s.rot_left(n.l)
      if n.l.l is not None and n.l.l.col == s.R:
        if n.r is not None and n.r.col == s.R:
          s.split(n)
          f = False
        else:
          n = s.rot_right(n)
    return n, f

  def check_right(s, n, f):
    if f:
      return n, f
    if n.col == s.B:
      f = True
      if n.r.l is not None and n.r.l.col == s.R:
        n.r = s.rot_right(n.r)
      if n.r.r is not None and n.r.r.col == s.R:
        if n.l is not None and n.l.col == s.R:
          s.split(n)
          f = False
        else:
          n = s.rot_left(n)
    return n, f

  def rot_left(s, n):
    rn = n.r
    n.r = rn.l
    rn.l = n
    rn.col = n.col
    n.col = s.R
    return rn
  
  def rot_right(s, n):
    ln = n.l
    n.l = ln.r
    ln.r = n
    ln.col = n.col
    n.col = s.R
    return ln

  def split(s, n):
    n.col = s.R
    n.l.col = s.B
    n.r.col = s.B

  def check_col(s, n, col):
    return n is not None and n.col == col

  def keep_right(s, n, f):
    if f:
      return n, f
    if s.check_col(n.l.l, s.B) and s.check_col(n.l.r, s.B):
      if n.l.col == s.B:
        n.l.col = s.R
        if n.col == s.B:
          return n, False
        n.col = s.B
      else:
        n = s.lot_right(n)
        n.r, _ = s.keep_right(n.r, False)
    else:
      if s.check_col(n.l.r, s.R):
        n.l = s.rot_left(n.l)
      n = s.rot_right(n)
      n.r.col = s.B
      n.l.col = s.B
      return n, True

  def keep_left(s, n, f):
    if f:
      return n, f
    if s.check_col(n.r.l, s.B) and s.check_col(n.r.r, s.B):
      if n.r.col == s.B:
        n.r.col = s.R
        if n.col == s.B:
          return n, False
        n.col = s.B
      else:
        n = s.lot_left(n)
        n.l, _ = s.keep_left(n.l, False)
    else:
      if s.check_col(n.r.l, s.R):
        n.r = s.rot_right(n.r)
      n = s.rot_left(n)
      n.l.col = s.B
      n.r.col = s.B
      return n, True

  def isNone(s):
    return s.root == None

  def get_min(s):
    return s.get_min_sub(s.root)

  def get_min_sub(s, n):
    while n.l is not None:
      n = n.l
    return n.data

  def delete(s, x):
    s.root, f = s.delete_sub(s.root, x)

  def delete_sub(s, n, x):
    if n is None:
      return n, True
    if x == n.data:
      if n.l is None and n.r is None:
        return None, n.col == s.R
      elif n.r is None:
        n.l.col = s.B
        return n.l, True
      elif n.l is None:
        n.r.col = s.B
        return n.r, True
      else:
        n.data = s.get_min_sub(n.r)
        n.r, f = s.delete_sub(n.r, n.data)
        return s.keep_right(n, f)
    elif x < n.data:
      n.l, f = s.delete_sub(n.l, x)
      return s.keep_left(n, f)
    else:
      n.r, f = s.delete_sub(n.r, x)
      return s.keep_right(n, f)

  def print_node(s, n, x):
    color = ("B", "R")
    if n is not None:
      s.print_node(n.l, x + 1)
      print("   " * x, color[n.col], n.data)
      s.print_node(n.r, x + 1)

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  L = []
  for s, t, x in STX:
    L.append([s - x, x])
    L.append([t - x, -x])
  L.sort()

  rbt = RBT()

  dc = 0
  lc = 0
  while dc < len(D):
    if lc == len(L) or D[dc] < L[lc][0]:
      if rbt.isNone():
        t = -1
      else:
        t = rbt.get_min()
      while lc == len(L) or D[dc] < L[lc][0]:
        print(t)
        dc += 1
        if dc == len(D):
          break
    else:
      while D[dc] >= L[lc][0]:
        k = L[lc][1]
        if k < 0:
          rbt.delete(-k)
        else:
          rbt.insert(k)
        lc += 1
        if lc == len(L):
          break

main()

Buggy submission (verdict: Runtime Error):
class RBT:
  B = 0
  R = 1

  class node:
    def __init__(s, x, col = 1):
      s.data = x
      s.col = col
      s.l = None
      s.r = None

  def __init__(s):
    s.root = None
    
  def insert(s, x):
    s.root, f = s.insert_sub(s.root, x)
    s.root.col = s.B

  def insert_sub(s, n, x):
    if n is None:
      return s.node(x), False
    if x < n.data:
      n.l, f = s.insert_sub(n.l, x)
      return s.check_left(n, f)
    else:
      n.r, f = s.insert_sub(n.r, x)
      return s.check_right(n, f)

  def check_left(s, n, f):
    if f:
      return n, f
    if n.col == s.B:
      f = True
      if n.l.r is not None and n.l.r.col == s.R:
        n.l = s.rot_left(n.l)
      if n.l.l is not None and n.l.l.col == s.R:
        if n.r is not None and n.r.col == s.R:
          s.split(n)
          f = False
        else:
          n = s.rot_right(n)
    return n, f

  def check_right(s, n, f):
    if f:
      return n, f
    if n.col == s.B:
      f = True
      if n.r.l is not None and n.r.l.col == s.R:
        n.r = s.rot_right(n.r)
      if n.r.r is not None and n.r.r.col == s.R:
        if n.l is not None and n.l.col == s.R:
          s.split(n)
          f = False
        else:
          n = s.rot_left(n)
    return n, f

  def rot_left(s, n):
    rn = n.r
    n.r = rn.l
    rn.l = n
    rn.col = n.col
    n.col = s.R
    return rn
  
  def rot_right(s, n):
    ln = n.l
    n.l = ln.r
    ln.r = n
    ln.col = n.col
    n.col = s.R
    return ln

  def split(s, n):
    n.col = s.R
    n.l.col = s.B
    n.r.col = s.B

  def check_col(s, n, col):
    return n is not None and n.col == col

  def keep_right(s, n, f):
    if f:
      return n, f
    if s.check_col(n.l.l, s.B) and s.check_col(n.l.r, s.B):
      if n.l.col == s.B:
        n.l.col = s.R
        if n.col == s.B:
          return n, False
        n.col = s.B
      else:
        n = s.lot_right(n)
        n.r, _ = s.keep_right(n.r, False)
    else:
      if s.check_col(n.l.r, s.R):
        n.l = s.rot_left(n.l)
      n = s.rot_right(n)
      n.r.col = s.B
      n.l.col = s.B
      return n, True

  def keep_left(s, n, f):
    if f:
      return n, f
    if s.check_col(n.r.l, s.B) and s.check_col(n.r.r, s.B):
      if n.r.col == s.B:
        n.r.col = s.R
        if n.col == s.B:
          return n, False
        n.col = s.B
      else:
        n = s.lot_left(n)
        n.l, _ = s.keep_left(n.l, False)
    else:
      if s.check_col(n.r.l, s.R):
        n.r = s.rot_right(n.r)
      n = s.rot_left(n)
      n.l.col = s.B
      n.r.col = s.B
      return n, True

  def isNone(s):
    return s.root == None

  def get_min(s):
    return s.get_min_sub(s.root)

  def get_min_sub(s, n):
    while n.l is not None:
      n = n.l
    return n.data

  def delete(s, x):
    s.root, f = s.delete_sub(s.root, x)

  def delete_sub(s, n, x):
    if n is None:
      return n, True
    if x == n.data:
      if n.l is None and n.r is None:
        return None, n.col == s.R
      elif n.r is None:
        n.l.col = s.B
        return n.l, True
      elif n.l is None:
        n.r.col = s.B
        return n.r, True
      else:
        n.data = s.get_min_sub(n.r)
        n.r, f = s.delete_sub(n.r, n.data)
        return s.keep_right(n, f)
    elif x < n.data:
      n.l, f = s.delete_sub(n.l, x)
      return s.keep_left(n, f)
    else:
      n.r, f = s.delete_sub(n.r, x)
      return s.keep_right(n, f)

  def print_node(s, n, x):
    color = ("B", "R")
    if n is not None:
      s.print_node(n.l, x + 1)
      print("   " * x, color[n.col], n.data)
      s.print_node(n.r, x + 1)

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

STX

L = []
for s, t, x in STX:
  L.append([s - x, x])
  L.append([t - x, -x])
L.sort()

rbt = RBT()

dc = 0
lc = 0
while dc < len(D):
  if lc == len(L) or D[dc] < L[lc][0]:
    if rbt.isNone():
      t = -1
    else:
      t = rbt.get_min()
    while lc == len(L) or D[dc] < L[lc][0]:
      print(t)
      dc += 1
      if dc == len(D):
        break
  else:
    while D[dc] >= L[lc][0]:
      k = L[lc][1]
      if k < 0:
        rbt.delete(-k)
      else:
        rbt.insert(k)
      lc += 1
      if lc == len(L):
        break