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: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
#……と思っていたけど、0になるイベントが複数あると、集合への出し入れがおかしくなる（0を複数入れたあと複数回だそうとするから、無いキーを出そうとしてしまう）
#時間がマイナスでもコード上全く問題無いんだから、外した！
  Events.append((s-x, 1, x))
  Events.append((t-x, -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=lambda x:-x[1])
Events = sorted(Events, key=lambda x:-x[0])
#発生タイミング（x[0]）が同じイベントは、集合からのout→inでも並び替える（x[1]について降順）。
#outより先にinが行われると、集合操作がおかしくなる

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
minstop = 10**9+1
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = nextevent
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
      minstop = min(c, minstop)
    else: #座標xの通行止めが解除される
      nowkeptout.remove(c)
      if c==minstop and nowkeptout: minstop = min(nowkeptout)
      elif not nowkeptout: minstop = 10**9+1
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 1, 1) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(minstop)
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Accepted

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
  Events.append((max(0,s-x), 1, x))
  Events.append((max(0,t-x), -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events = Events[::-1] #降順にする reverseを使うのは、「ひっくり返した状態で」安定じゃないとイベントの入力順がズレてエラーが出るため。reverseを使うと、キーが重複している場合は元の順番を保ってしまう（ひっくり返すと、キーが重複している部分に限っては元の順番と反対になってしまい、「存在しない値を集合からひこうとする」というエラーになる）

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
minstop = 10**9+1
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = nextevent
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
      minstop = min(c, minstop)
    else: #座標xの通行止めが解除される
      try:
          nowkeptout.remove(c)
      except: 
          pass
      if c==minstop and nowkeptout: minstop = min(nowkeptout)
      elif not nowkeptout: minstop = 10**9+1
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 1, 1) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(minstop)
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
    events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
m = float('inf')
for e in events:
    if e[1] == 0:
        block.remove(e[2])
        if m == e[2]:
            if block:
                m = min(block)
            else:
                m = float('inf')
    elif e[1] == 1:
        block.add(e[2])
        m = min(m, e[2])
    else:
        if block:
            if m == float('inf'):
                ans[e[2]] = -1
            else:
                ans[e[2]] = m
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from bisect import bisect_left

n,q=map(int,input().split())
work=[list(map(int,input().split())) for _ in range(n)]
work=sorted(work,key=lambda x:x[2])
pos=[int(input()) for _ in range(q)]
ans=[-1]*q
checked=[-1]*q
for s,t,x in work:
  l=bisect_left(pos,s-x)
  r=bisect_left(pos,t-x)
  while l<r:
    if checked[l]==-1:
      checked[l]=r
      ans[l]=x
      l+=1
    else:
      l=checked[l]
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',r"""
def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l//=2
            r//=2
    a=[]
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        a.append(-(s==I)or s)
    print('\n'.join(map(str,a)))
main()
"""))

Submission status: Accepted

Solution code:
import sys
import bisect
input=sys.stdin.readline

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

construction = [list(map(int, input().split(' '))) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
construction = sorted(construction, key=lambda x: x[2])

dist = [-1] * Q
jump = [-1] * Q
indices = list(range(Q))
for s, t, x in construction:
    i1 = bisect.bisect_left(D, s-x)
    i2 = bisect.bisect_left(D, t-x)
    i = i1
    while i < i2:
        k = jump[i]
        if k != -1:
            i = k
        else:
            jump[i] = i2
            dist[i] = x
            i += 1
    
for d in dist:
    print(d)

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys

input = sys.stdin.readline

inf = float('inf')

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

es = []
for _ in range(N):
    s, t, x = map(int, input().split())
    es.append((s - x, 1, x))
    es.append((t - x - 0.5, -1, x))

es.sort(key=itemgetter(0))
st = set()
cur_min_stop = inf
check_needed = True

# print(es)
i = 0
for _ in range(Q):
    d = int(input())
    while i < N * 2:
        time, typ, pos = es[i]
        # print(es[i])
        if time > d:
            break
        if typ == 1:
            st.add(pos)
            if pos < cur_min_stop:
                cur_min_stop = pos
        else:
            st.remove(pos)
            if pos == cur_min_stop:
                check_needed = True
        i = i + 1

    if check_needed:
        if st:
            cur_min_stop = min(st)
        else:
            cur_min_stop = inf
        check_needed = False
    print(cur_min_stop if cur_min_stop < inf else -1)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n,m = m()

l = [l() for i in range(n)]
l.sort(key = lambda x:x[2])
ans = [-1]*m
ju = [-1]*m
d = [onem() for i in range(m)]
for s,t,x in l:
    ore = bs.bisect_left(d,s-x)
    o = bs.bisect_left(d,t-x)
    while (ore < o):
        k = ju[ore]
        if k == -1:
            ans[ore] = x
            ju[ore] = o
            ore += 1
        else:
            ore = k
for i in range(m):
    print(ans[i])

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, Q = map(int, input().split())
S, T, X = [0] * N, [0] * N, [0] * N
work = []

for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	work.append((X[i], S[i] - X[i], T[i] - X[i]))

D = [int(input()) for _ in range(Q)]

work.sort()
ans = [-1] * Q
skip = [-1] * Q

for i in range(N):
	left = bisect.bisect_left(D, work[i][1])
	right = bisect.bisect_left(D, work[i][2])
	
	while left < right:
		if skip[left] == -1:
			skip[left] = right
			ans[left] = work[i][0]
			left += 1
		else:
			left = skip[left]					
		
for i in ans:
	print(i)

Submission status: Accepted

Solution code:
import bisect
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
STX=[list(map(int,input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2])
ans=[-1]*Q
jump=[-1]*Q
D=[int(input()) for i in range(Q)]
for s,t,x in STX:
    l=bisect.bisect_left(D,s-x)
    r=bisect.bisect_left(D,t-x)
    while(l<r):
        k=jump[l]
        if k==-1:
            ans[l]=x
            jump[l]=r
            l+=1
        else:
            l=k
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
import bisect
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2])
ans=[-1]*Q
jump=[-1]*Q
D=[int(input()) for i in range(Q)]
for s,t,x in STX:
    l=bisect.bisect_left(D,s-x)
    r=bisect.bisect_left(D,t-x)
    while(l<r):
        k=jump[l]
        if k==-1:
            ans[l]=x
            jump[l]=r
            l+=1
        else:
            l=k
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
import heapq
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

events = []
for s, t, x in stx:
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events.sort(key=lambda x: x[0])

hp = []
st = set()
res = [-1] * q
now = 0
for t, b, x in events:
    while now < q and d[now] < t:
        if len(st) > 0:
            while hp[0] not in st:
                heapq.heappop(hp)
            res[now] = hp[0]
        now += 1
    if b == 1:
        heapq.heappush(hp, x)
        st.add(x)
    else:
        st.discard(x)
print(*res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
E - Roadwork
https://atcoder.jp/contests/abc128/tasks/abc128_e

"""
import sys

from heapq import heappop, heappush

def solve(N, Q):
    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    events.sort(reverse=True)
    D = [int(input()) for _ in range(Q)]

    blocked = set()
    ans = []
    hq = []
    for d in D:
        while events and events[-1][0] <= d:
            t, e, x = events.pop()
            if e == -1:
                blocked.discard(x)
            else:
                blocked.add(x)
                heappush(hq, x)
        if blocked:
            while hq and hq[0] not in blocked:
                heappop(hq)
            ans.append(hq[0] if hq else -1)
        else:
            ans.append(-1)
    return ans


def main(args):
    N, Q = map(int, input().split())
    ans = solve(N, Q)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import heapq as hq
from collections import defaultdict
N, Q = map(int, input().split())
event = []
for i in range(N):
    si, ti, xi = map(int, input().split())
    event.append([si - xi, ti - xi, xi])
#STX = [list(map(int, input().split())) for i in range(N)]
Dlist = [int(input()) for i in range(Q)]
#for s,t,x in STX:
#    event.append([s - x, t-x, x])
event.sort(key=lambda x:x[0])
h = []
tdic = defaultdict(int)
ind = 0
for Di in Dlist:
    while ind<N and event[ind][0] <= Di:
        #Diまでに始まった工事を追加
        hq.heappush(h, event[ind][2])
        tdic[event[ind][2]] = event[ind][1]
        ind += 1
    while h and Di >= tdic[h[0]]:
        #Diまでに終わった工事を削除
        hq.heappop(h)
    if h:
        print(h[0])
    else:
        print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect

N,Q = (int(x) for x in input().split())

stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]

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

ans_arr = [-1]*Q
skip_arr = [-1]*(Q+1)

def update_skip(skip_arr, x):
    if skip_arr[x] == -1:
        return x
    x_dest = update_skip(skip_arr, skip_arr[x])
    skip_arr[x] = x_dest
    return x_dest

for s,t,x in stop_arr:
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    l = q_start
    while l < q_stop:
        if skip_arr[l] == -1:
            skip_arr[l] = q_stop
            ans_arr[l] = x
            l += 1
        else:
            l = update_skip(skip_arr, l)

print(*ans_arr, sep="\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect

N,Q = (int(x) for x in input().split())

stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]

stop_arr_ind = list(range(N))
stop_arr_ind.sort(key=lambda x:stop_arr[x][2])

ans_arr = [-1]*Q
skip_arr = [-1]*(Q+1)

def update_skip(skip_arr, x):
    if skip_arr[x] == -1:
        return x
    x_dest = update_skip(skip_arr, skip_arr[x])
    skip_arr[x] = x_dest
    return x_dest

for i in stop_arr_ind:
    s,t,x = stop_arr[i]
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    l = q_start
    while l < q_stop:
        if skip_arr[l] == -1:
            skip_arr[l] = q_stop
            ans_arr[l] = x
            l += 1
        else:
            l = update_skip(skip_arr, l)

print(*ans_arr, sep="\n")

Submission status: Accepted

Solution code:
from bisect import bisect_left

N,Q = (int(x) for x in input().split())

stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]

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

ans_arr = [-1]*Q
skip_arr = [-1]*(Q+1)

for s,t,x in stop_arr:
    q_start = bisect_left(Q_arr, s-x)
    q_stop = bisect_left(Q_arr, t-x)
    l = q_start
    while l < q_stop:
        if skip_arr[l] == -1:
            skip_arr[l] = q_stop
            ans_arr[l] = x
            l += 1
        else:
            l = skip_arr[l]

print(*ans_arr, sep="\n")

Submission status: Accepted

Solution code:
import bisect

N,Q = (int(x) for x in input().split())

stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]

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

ans_arr = [-1]*Q
skip_arr = [-1]*(Q+1)

for s,t,x in stop_arr:
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    l = q_start
    while l < q_stop:
        if skip_arr[l] == -1:
            skip_arr[l] = q_stop
            ans_arr[l] = x
            l += 1
        else:
            l = skip_arr[l]

print(*ans_arr, sep="\n")

Submission status: Accepted

Solution code:
import bisect

N,Q = (int(x) for x in input().split())

stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]

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

ans_arr = [-1]*Q
skip_arr = [-1]*(Q+1)

def update_skip(skip_arr, x):
    if skip_arr[x] == -1:
        return x
    x_dest = update_skip(skip_arr, skip_arr[x])
    skip_arr[x] = x_dest
    return x_dest

for s,t,x in stop_arr:
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    l = q_start
    while l < q_stop:
        if skip_arr[l] == -1:
            skip_arr[l] = q_stop
            ans_arr[l] = x
            l += 1
        else:
            l = update_skip(skip_arr, l)

print(*ans_arr, sep="\n")

Submission status: Accepted

Solution code:
import bisect

N,Q = (int(x) for x in input().split())

stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]

stop_arr_ind = list(range(N))
stop_arr_ind.sort(key=lambda x:stop_arr[x][2])
# stop_arr.sort(key=lambda x:x[2], reverse=True)
ans_arr = [-1]*Q
skip_arr = [-1]*(Q+1)

def update_skip(skip_arr, x):
    if skip_arr[x] == -1:
        return x
    x_dest = update_skip(skip_arr, skip_arr[x])
    skip_arr[x] = x_dest
    return x_dest

for i in stop_arr_ind:
    s,t,x = stop_arr[i]
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    l = q_start
    while l < q_stop:
        if skip_arr[l] == -1:
            skip_arr[l] = q_stop
            ans_arr[l] = x
            l += 1
        else:
            l = update_skip(skip_arr, l)

print(*ans_arr, sep="\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
rl = lambda: map(int, input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append((s-x-0.5,1,x))
    TT.append((t-x-0.5,-1,x))
for i in range(Q):
    d = ri()
    TT.append((d,0,i))


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
rl = lambda: [int(x) for x in input().split()]
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append((s-x-0.5,1,x))
    TT.append((t-x-0.5,-1,x))
for i in range(Q):
    d = ri()
    TT.append((d,0,i))


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append((s-x-0.5,1,x))
    TT.append((t-x-0.5,-1,x))
for i in range(Q):
    d = ri()
    TT.append((d,0,i))


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
#5814544

from bisect import bisect_left

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

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

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

ans = [-1]*Q
skip = [-1]*Q

for s,t,x in STX:
    left = bisect_left(D,s-x)
    right = bisect_left(D,t-x)

    while left < right:
        if skip[left] == -1:
            ans[left] = x
            skip[left] = right
            left += 1
        else:
            left = skip[left]
    
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N, Q = map(int, input().split())
W = [tuple(map(int, input().split())) for _ in range(N)]
W.sort(key=lambda x:x[2])
D = [int(input()) for _ in range(Q)]
ans = [-1]*Q
skip = [-1]*Q
for s, t, x in W:
    l = bisect_left(D, s-x)
    r = bisect_left(D, t-x)
    while l < r:
        if skip[l] == -1:
            ans[l] = x
            skip[l] = r
            l += 1
        else:
            l = skip[l]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
MOD = 10 ** 9 + 7

def main(): 
    N, Q = LI()
    STX = []
    for _ in range(N):
        STX.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())

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

    ans = [-1] * Q
    skip = [-1] * Q

    from bisect import bisect_left
    for s, t, x in STX:
        left = bisect_left(D, s-x)  # s-x を超える最小のdの位置
        right = bisect_left(D, t-x)  # t-x を超える最小のdの位置

        while left < right:
            if skip[left] == -1:  # 未踏
                ans[left] = x
                skip[left] = right  # つぎにここにきた際は、rightまで見るのをスキップしてよい。
                left += 1
            else:  # 来たことがある
                left = skip[left]  # 以前覚えておいた right まで見るのをスキップする。

    for i in ans: print(i)

main()

Submission status: Accepted

Solution code:
from ctypes import *
import subprocess as sp
from operator import itemgetter
import sys
import os.path

# C++のstd::setのラッパー。こいつを呼び出す。
set_code = r"""
#include <set>

std::set<int> s;

void add(int x) {
    s.insert(x);
}

bool find(int x) {
    return s.find(x) != s.end();
}

void remove(int x) {
    s.erase(x);
}

bool empty() {
	return s.empty();
}

int getMin() {
	return *s.begin();
}
"""

class CppSet:
	# オブジェクトが作られた数
	# オブジェクトごとに共有ライブラリを作成する必要があるので、counterで共有ライブラリにIDを割り振る
	counter = 0

	def __init__(self):
		# 共有ライブラリを作成して、それを呼び出す
		lib_name = './hoge{}.so'.format(CppSet.counter)

		# C++のソースを書き出します
		code_file_name = "tmp.cpp"
		with open(code_file_name, "w") as f:
			f.write(set_code)

		CppSet.counter += 1 

		# 共有ライブラリを作成。-std=c++14とかにすると動かなくなる
		sp.Popen(['g++', '-fPIC', '-shared', '-std=c++11', '-O2', code_file_name, '-o', lib_name]).communicate()

		# Pythonから共有ライブラリを召喚します
		# 召喚方法は https://over80.hatenadiary.jp/entry/20150816/pure_python_inotify を参照
		# 上で書いたコードのgetMinとかの関数が、共有ライブラリではシンボルに変換される(マングリング)らしい
		# なので、シンボルから関数名を得るためにデマングルとかいうやつをやります
		# 最終的にシンボルと関数の対応関係を使って、各関数を召喚します
		# マングリング: https://albel06.hatenablog.com/entry/2016/03/17/180000
		# デマングル: http://0xcc.net/blog/archives/000095.html
		lib = CDLL(lib_name)
		self.add = getattr(lib, "_Z3addi")
		self.find = CFUNCTYPE(c_bool, c_int)(
						("_Z4findi", lib),
						((1, "x"), )
					)
		self.remove = getattr(lib, "_Z6removei")
		self.empty = CFUNCTYPE(c_bool)(
						("_Z5emptyv", lib),
						()
					)

		self.getMin = CFUNCTYPE(c_int)(
						("_Z6getMinv", lib),
						()
					)

def main():
	N, Q = map(int, sys.stdin.readline().split())
	tmp = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
	stx = [(s - x, 1, x) for s, t, x in tmp] + [(t - x, -1, x) for s, t, x in tmp]
	stx.sort()
	
	D = [int(sys.stdin.readline()) for _ in range(Q)] 
	ans = [-1]*Q

	idx = 0
	stx_len = len(stx)
	se = CppSet()
	for i, d in enumerate(D):
		while idx < stx_len:
			t, com, x = stx[idx]
			if t > d:
				break
			if com == 1:
				se.add(x)
			else:
				se.remove(x)
			idx += 1
		ans[i] = (-1 if se.empty() else se.getMin())

	print(*ans, sep='\n')

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from ctypes import *
import subprocess as sp
from operator import itemgetter
import sys
import os.path

set_code = r"""
#include <set>

std::set<int> s;

void add(int x) {
    s.insert(x);
}

bool find(int x) {
    return s.find(x) != s.end();
}

void remove(int x) {
    s.erase(x);
}

bool empty() {
	return s.empty();
}

int getMin() {
	return *s.begin();
}
"""

class CppSet:
	counter = 0

	def __init__(self):
		lib_name = './hoge{}.so'.format(CppSet.counter)

		code_file_name = "tmp.cpp"
		with open(code_file_name, "w") as f:
			f.write(set_code)

		CppSet.counter += 1
		sp.Popen(['g++', '-fPIC', '-shared', '-std=c++11', '-O2', code_file_name, '-o', lib_name]).communicate()

		lib = CDLL(lib_name)
		self.add = getattr(lib, "_Z3addi")
		self.find = CFUNCTYPE(c_bool, c_int)(
						("_Z4findi", lib),
						((1, "x"), )
					)
		self.remove = getattr(lib, "_Z6removei")
		self.empty = CFUNCTYPE(c_bool)(
						("_Z5emptyv", lib),
						()
					)

		self.getMin = CFUNCTYPE(c_int)(
						("_Z6getMinv", lib),
						()
					)

def main():
	N, Q = map(int, sys.stdin.readline().split())
	tmp = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
	stx = [(s - x, 1, x) for s, t, x in tmp] + [(t - x, -1, x) for s, t, x in tmp]
	stx.sort()
	
	D = [int(sys.stdin.readline()) for _ in range(Q)] 
	ans = [-1]*Q

	idx = 0
	stx_len = len(stx)
	se = CppSet()
	for i, d in enumerate(D):
		while idx < stx_len:
			t, com, x = stx[idx]
			if t > d:
				break
			if com == 1:
				se.add(x)
			else:
				se.remove(x)
			idx += 1
		ans[i] = (-1 if se.empty() else se.getMin())

	print(*ans, sep='\n')

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from ctypes import *
import subprocess as sp
from operator import itemgetter
import sys
import os.path

set_code = r"""
#include <set>

std::set<int> s;

void add(int x) {
    s.insert(x);
}

bool find(int x) {
    return s.find(x) != s.end();
}

void remove(int x) {
    s.erase(x);
}

bool empty() {
	return s.empty();
}

int getMin() {
	return *s.begin();
}
"""

class CppSet:
	counter = 0

	def __init__(self):
		lib_name = './hoge{}.so'.format(CppSet.counter)

		if not os.path.exists(lib_name):
			code_file_name = "tmp.cpp"
			with open(code_file_name, "w") as f:
				f.write(set_code)

			CppSet.counter += 1
			sp.Popen(['g++', '-fPIC', '-shared', '-std=c++11', code_file_name, '-o', lib_name]).communicate()

		lib = CDLL(lib_name)
		self.add = getattr(lib, "_Z3addi")
		self.find = CFUNCTYPE(c_bool, c_int)(
						("_Z4findi", lib),
						((1, "x"), )
					)
		self.remove = getattr(lib, "_Z6removei")
		self.empty = CFUNCTYPE(c_bool)(
						("_Z5emptyv", lib),
						()
					)

		self.getMin = CFUNCTYPE(c_int)(
						("_Z6getMinv", lib),
						()
					)

def main():
	N, Q = map(int, sys.stdin.readline().split())
	tmp = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
	stx = [(s - x, 1, x) for s, t, x in tmp] + [(t - x, -1, x) for s, t, x in tmp]
	stx.sort()
	
	D = [int(sys.stdin.readline()) for _ in range(Q)] 
	ans = [-1]*Q

	idx = 0
	stx_len = len(stx)
	se = CppSet()
	for i, d in enumerate(D):
		while idx < stx_len:
			t, com, x = stx[idx]
			if t > d:
				break
			if com == 1:
				se.add(x)
			else:
				se.remove(x)
			idx += 1
		ans[i] = (-1 if se.empty() else se.getMin())

	print(*ans, sep='\n')

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from bisect import bisect_left

n, q = li()

stx = [list(li()) for _ in range(n)]
d = [ni() for _ in range(q)]

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

ans = [-1]*q
skip = [-1]*q

for si, ti, xi in stx:
    left = bisect_left(d, si-xi)
    right = bisect_left(d, ti-xi)

    while left < right:
        if skip[left] == -1:
            ans[left] = xi
            skip[left] = right
            left += 1

        else:
            left = skip[left]

print(*ans, sep="\n")