Problem:


Score : 500 points

Problem Statement

There is an infinitely long street that runs west to east, which we consider as a number line.

There are N roadworks scheduled on this street.
The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.

Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the Q people will walk.

Constraints

All values in input are integers.

1 \leq N, Q \leq 2 \times 10^5

0 \leq S_i < T_i \leq 10^9

1 \leq X_i \leq 10^9

0 \leq D_1 < D_2 < ... < D_Q \leq 10^9

If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Input

Input is given from Standard Input in the following format:

N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q

Output

Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

Sample Input 1

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

Sample Output 1

2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.

The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.

The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.



Sample input:
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8


Sample output:
2
2
10
-1
13
-1

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
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

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline

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

event = []
spot_set = set()
for stop in stops:
    d = stop[2]
    start = stop[0] - d
    finish = stop[1] - d
    event.append([start, 1, d])
    event.append([finish, -1, d])

event.sort(key=lambda x: x[0])

for i in range(len(event)):
    e = event[i]
    if e[1] == 1:
        spot_set.add(e[2])
    else:
        spot_set.remove(e[2])
    while len(D) > 0 and i < len(event)-1 and D[0] < event[i+1][0]:
        if len(spot_set) > 0:
            print(min(spot_set))
        else:
            print("-1")
        D.pop(0)

for d in D:
    print("-1")

Submission status: Runtime Error

Solution code:
import sys,bisect,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,q = inm()
stx = []
for i in range(n):
    s,t,x = inm()
    stx.append((s,t,x))
d = []
for i in range(q):
    x = inn()
    d.append(x)

ls = [ [] for i in range(q) ]
rs = [ [] for i in range(q) ]
for i in range(n):
    s,t,x = stx[i]
    if t-x <= d[0] or d[q-1] < s-x:
        continue
    l = bisect.bisect_left(d,s-x)
    r = bisect.bisect_left(d,t-x)
    ddprint("s {} t {} x {} l {} r {}".format(s,t,x,l,r))
    ls[l].append(x)
    rs[r].append(x)

ddprint(ls)
ddprint(rs)
dist = [0] * q
hp = []
mark = defaultdict(bool)
for i in range(q):
    for z in rs[i]:
        mark[z] = True
    for z in ls[i]:
        heapq.heappush(hp,z)
        mark[z] = False
    while len(hp)>0 and mark[hp[0]]:
        heapq.heappop(hp)
    dist[i] = -1 if len(hp)==0 else hp[0]

for i in range(q):
    print(dist[i])

Submission status: Runtime Error

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math
import heapq


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


# n : kouji count
def main():
    n, q = intin()
    stxlist = intinl(n)
    dlist = intinl(q)

    stxlist = [(s - x, t - x, x) for s, t, x in stxlist]

    event_list = []
    for s, t, x in stxlist:
        event_list.append((s, 1, x))
        event_list.append((t, -1, x))

    for d in dlist:
        event_list.append((d, 2, 0))

    event_list.sort()

    stop_list = []
    remove_list = []
    for time, event, x in event_list:
        if event == 2:
            if stop_list:
                print(stop_list[0])
            else:
                print(-1)
        if event == 1:
            heapq.heappush(stop_list, x)
        if event == -1:
            if stop_list[0] == x:
                heapq.heappop(stop_list)
            else:
                heapq.heappush(remove_list, x)
                while remove_list[0] == stop_list[0]:
                    heapq.heappop(remove_list)
                    heapq.heappop(stop_list)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
constraction = [list(map(int, input().split())) for _ in range(N)]
constraction = sorted(constraction, key=lambda x: x[0] + x[2])
ignore = []
for i in range(N):
    s, t, x = constraction[i]
    for j in range(i + 1, N):
        ns, nt, nx = constraction[j]
        if s + x < ns + nx < t + x:
            ignore.append(j)
for j in ignore[::-1]:
    constraction.pop(j)
constraction = sorted(constraction, key=lambda x: x[2])
D = list(int(input()) for _ in range(Q))
for q in D:
    ignore = []
    for i in range(len(constraction)):
        s, t, x = constraction[i]
        if x < t - q:
            if s - q <= x:
                print(x)
                for j in ignore[::-1]:
                    constraction.pop(j)
                break
        else:
            ignore.append(i)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    nexts = [-1] * Q
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        to = end
        while nexts[to] != -1:
            to = nexts[to]
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = to
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    skip = [0] * Q
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        while i < end:
            while skip[i] != 0:
                i += skip[i]
            if i >= end:
                break
            ans[i] = x
            skip[i] = end - i
            i += 1
    for y in ans:
        print(y)
    return

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    skip = [0] * Q
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        while i < end:
            while skip[i] != 0:
                i += skip[i]
                if i >= end:
                    break
            ans[i] = x
            skip[i] = end - i
            i += 1
    for y in ans:
        print(y)
    return

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    skip = [0] * Q
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        while i < end:
            while skip[i] != 0:
                i += skip[i]
                if i > end:
                    break
            ans[i] = x
            skip[i] = end - i
            i += 1
    for y in ans:
        print(y)
    return

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    nexts = [-1] * Q
    for x, s, t in XST:
        i0 = bisect_left(D, s)
        i = i0
        while D[i] < t:
            if nexts[i] == -1:
                ans[i] = x
                i += 1
            else:
                i = nexts[i]
        end = i
        for i in range(i0, end):
            if nexts[i] != -1:
                break
            else:
                nexts[i] = end
                i += 1
    for y in ans:
        print(y)
    return

main()

Submission status: Runtime Error

Solution code:
from heapq import *
input = sys.stdin.readline
n,Q = list(map(int, input().split()))
Y=[]
for j in range(n):
    a=list(map(int, input().split()))
    Y.append([a[0]-a[2],a[1]-a[2],a[2]])
q = [int(input()) for i in range(Q)]
Y.sort()
X=[]
p=0
for d in q:
    while p<n and Y[p][0]<=d:
        heappush(X,(Y[p][2],Y[p][1]))
        p+=1
    while X and X[0][1] <= d:
        heappop(X)
    if X:
        print(X[0][0])
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) # xで死ぬ
  heappush(q,(t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = []
remove_task = []

while q:
  a,c,b = heappop(q)
  if not c:
    heappush(remove_task,b)
  elif c&1:
    heappush(se,b)
  else:
    while se:
      x = se[0]
      y = remove_task[0]
      if x == y:
        se.pop()
        remove_task.pop()
        continue
      else:
        answer[b] = x

print('\n'.join(map(str,answer)))

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_right
from operator import itemgetter

input = sys.stdin.readline

N, Q = map(int, input().split())

e = []
for _ in range(N):
    S, T, X = map(int, input().split())
    e.append([S - X, 1, X])
    e.append([T - X, -1, X])
e = sorted(e, key=itemgetter(0))

s1, s2 = [], []
tmp = set()
for t, p, x in e:
    if p == 1:
        tmp.add(x)
    else:
        tmp.remove(x)
    s1.append(t)
    s2.append(tmp.copy())

for i in range(Q):
    D = int(input())
    i = bisect_right(s1, D)
    s = {}
    if i > 0:
        s = s2[i - 1]
    if len(s) > 0:
        ans = min(s)
    else:
        ans = -1
    print(ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
import sys

ans = [None]*Q
def solve():
    readline = sys.stdin.readline
    N, Q = map(int, readline().split())
    qs = [0]*(N+1)
    for i in range(N):
        s, t, x = map(int, readline().split())
        qs[i] = (s-x, t-x, x)
    qs[N] = (10**10, 10**10, 0)
    qs.sort()

    que = []
    D = [int(readline()) for i in range(Q)]
    j = 0
    it = iter(qs).__next__
    s, t, x = it()
    v = w = N
    for d in D:
        while j < N and s <= d:
            heappush(que, (x, t))
            v, w = que[0]
            s, t, x = it()
        while que and w <= d:
            heappop(que)
            if que:
                v, w = que[0]
        if que:
            yield "%d\n" % v
        else:
            yield "-1\n"
ans[:] = solve()
sys.stdout.writelines(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, Q = LI()
    events = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        events.append([s, x])
        events.append([t, -x])
    for _ in range(Q):
        d = II()
        events.append([d, INF])
    events.sort()
    dst = {}
    for t, x in events:
        if x == INF: # query
            y = min(dst) if len(dst) else -1
            print(y)
        elif x > 0: # add
            dst.add(x)
        else: # x < 0, delete
            dst.remove(-x)
    return

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, Q = LI()
    events = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        events.append([s, x])
        events.append([t, -x])
    for _ in range(Q):
        d = II()
        events.append([d, INF])
    events.sort()
    dst = {}
    for t, x in events:
        if x == INF: # query
            y = min(dst) if dst else -1
            print(y)
        elif x > 0: # add
            dst.add(x)
        else: # x < 0, delete
            dst.remove(-x)
    return

main()