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: Time Limit Exceeded

Solution code:
### 解説見てから書いたコード
n, q = map(int, input().split())
events = []
stop_points = []
for i in range(n):
    si, ti, xi = map(int, input().split())
    events.append([si-xi,  True, xi])
    events.append([ti-xi, False, xi])
d = [int(input()) for i in range(q)]
events.sort()

def do_event(flag, xi):
    if flag:
        stop_points.append(xi)
    else:
        stop_points.remove(xi)

event_i = 0
events_len = len(events)
for di in d:
    while event_i < events_len and events[event_i][0] <= di:
        do_event(events[event_i][1], events[event_i][2])
        event_i += 1
    d_stop = -1 if len(stop_points) == 0 else min(stop_points)
    print(d_stop)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
# s, t = [], []
x = []
stops = []
for i in range(n):
    si, ti, xi = map(int, input().split())
    # s.append(si); t.append(ti);
    x.append(xi)
    stops.append(range(si-xi, ti-xi))
d = [int(input()) for i in range(q)]

max_x = max(x)
for i, di in enumerate(d):
    di_stop = max_x
    is_di_stop = False
    for j, stop in enumerate(stops):
        if di in stop:
            di_stop = min(di_stop, x[j])
            is_di_stop = True
    if not is_di_stop:
        di_stop = -1
    print(di_stop)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

construction = [list(map(int, input().rstrip().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 c in construction:
    i1 = bisect.bisect_left(D, c[0] - c[2])
    i2 = bisect.bisect_left(D, c[1] - c[2])
    i = i1
    while i < i2:
        if jump[i] != -1:
            i = jump[i]
            continue
        else:
            jump[i] = i2
            dist[i] = c[2]
            i += 1
    
for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

d2i = dict([(d, i) for i, d in enumerate(D)])
dist = [-1] * Q
indices = list(range(Q))
for c in construction:
    i1 = bisect.bisect_left(D, c[0] - c[2])
    i2 = bisect.bisect_left(D, c[1] - c[2])
    for i in range(i1, i2):
        dist[d2i[D[i]]] = c[2]
    del D[i1:i2]
    
for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

d2i = dict([(d, i) for i, d in enumerate(D)])
dist = [-1] * Q
indices = list(range(Q))
for c in construction:
    i1 = bisect.bisect_left(D, c[0] - c[2])
    i2 = bisect.bisect_left(D, c[1] - c[2])
    for i in range(i2-1, i1-1, -1):
        d = D.pop(i)
        dist[d2i[d]] = c[2]
    
for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

dist = [-1] * Q
indices = list(range(Q))
for c in construction:
    i1 = bisect.bisect_left(D, c[0] - c[2])
    i2 = bisect.bisect_left(D, c[1] - c[2])
    for i in list(range(i1, i2))[::-1]:
        D.pop(i)
        dist[indices[i]] = c[2]
        indices.pop(i)
    
for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

dist = [-1] * Q
for c in construction:
    i1 = bisect.bisect_left(D, c[0] - c[2])
    i2 = bisect.bisect_left(D, c[1] - c[2])
    for i in range(i1, i2):
        dist[i] = c[2]
    
for d in dist:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect, sys

def main():
    input = sys.stdin.readline
    N, Q = map(int,input().split())
    E = []
    append = E.append
    for k in range(N):
        s, e, x = map(int,input().split())
        append([x,s-x,e-x])
    D = [int(input()) for k in range(Q)]
    E.sort()
    ans = {d:-1 for d in D}
    bi = bisect.bisect_left
    for e in E:
        t = bi(D,e[1])
        while t < Q:
            if D[t] < e[2]:
                if ans[D[t]] == -1:
                    ans[D[t]] = e[0]
                t += 1
            else:
                break
    for k in range(Q):
        print(ans[D[k]])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    es.append((int(input()), 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = inf
check_needed = True
d_cnt = 0
for time, typ, pos in es:
    if typ == 1:
        st.add(pos)
        if pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        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)
        d_cnt += 1
        if d_cnt == Q:
            break

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    es.append((int(input()), 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = inf
check_needed = True
d_cnt = 0
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        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)
        d_cnt += 1
        if d_cnt == Q:
            break

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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, x))

for _ in range(Q):
    d = int(input())
    es.append((d, 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = -1
check_needed = True
d_cnt = 0
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if cur_min_stop == -1 or pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = -1
            check_needed = False
        print(cur_min_stop)
        d_cnt += 1
        if d_cnt == Q:
            break

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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, x))

for _ in range(Q):
    d = int(input())
    es.append((d, 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = -1
check_needed = True
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if cur_min_stop == -1 or pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = -1
            check_needed = False
        print(cur_min_stop)

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    d = int(input())
    es.append((d, 2, -1))

es.sort(key=lambda x: (x[0], x[1]))
st = set()
cur_min_stop = -1
check_needed = True
for i, (time, typ, pos) in enumerate(es):
    # print(es)
    # print(st)
    # print(i, (time, typ, pos))
    if typ == 1:
        st.add(pos)
        if cur_min_stop == -1 or pos < cur_min_stop:
            cur_min_stop = pos
    elif typ == 0:
        st.remove(pos)
        if pos == cur_min_stop:
            check_needed = True
    else:
        if check_needed:
            if st:
                cur_min_stop = min(st)
            else:
                cur_min_stop = -1
            check_needed = False
        print(cur_min_stop)

Submission status: Time Limit Exceeded

Solution code:
import bisect
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: Time Limit Exceeded

Solution code:
import bisect
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: Time Limit Exceeded

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

def main():
	N, Q = map(int, input().split())
	S, T, X = [0] * N, [0] * N, [0] * N
	
	for i in range(N):
		S[i], T[i], X[i] = map(int, input().split())
		
	D = [int(input()) for _ in range(Q)]
	
	event = [] #工事と人を１つのリストで管理: (時間, 出来事の種類, [工事の位置])
	#出来事の種類: (0: 工事の終了、1: 工事の開始、2: 人)
	working = [] #現在行われている工事のリスト
	n = 0 #現在行われている工事の数
	
	for i in range(Q):
		event.append((D[i], 2))
		
	for i in range(N):
		bisect.insort(event, (S[i] - X[i] - 0.5, 1, X[i]))
		bisect.insort(event, (T[i] - X[i] - 0.5, 0, X[i]))
		
	for l in event:
		if l[1] == 1:
			bisect.insort(working, l[2])
			n += 1
		elif l[1] == 0:
			del working[bisect.bisect(working, l[2]) - 1]
			n -= 1
		else:
			if n > 0:
				print(working[0])
			else:
				print(-1)
				
main()

Submission status: Time Limit Exceeded

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

for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	
D = [int(input()) for _ in range(Q)]

event = [] #工事と人を１つのリストで管理: (時間, 出来事の種類, [工事の位置])
#出来事の種類: (0: 工事の終了、1: 工事の開始、2: 人)
working = [] #現在行われている工事のリスト
n = 0 #現在行われている工事の数

for i in range(Q):
	event.append((D[i], 2))
	
for i in range(N):
	bisect.insort(event, (S[i] - X[i] - 0.5, 1, X[i]))
	bisect.insort(event, (T[i] - X[i] - 0.5, 0, X[i]))
	
for l in event:
	if l[1] == 1:
		bisect.insort(working, l[2])
		n += 1
	elif l[1] == 0:
		del working[bisect.bisect(working, l[2]) - 1]
		n -= 1
	else:
		if n > 0:
			print(working[0])
		else:
			print(-1)

Submission status: Time Limit Exceeded

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

for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	
D = [int(input()) for _ in range(Q)]

event = [] #工事と人を１つのリストで管理: (時間, 出来事の種類, [工事の位置])
#出来事の種類: (0: 工事の終了、1: 工事の開始、2: 人)
working = [] #現在行われている工事のリスト

for i in range(Q):
	event.append((D[i], 2))
	
for i in range(N):
	bisect.insort(event, (S[i] - X[i] - 0.5, 1, X[i]))
	bisect.insort(event, (T[i] - X[i] - 0.5, 0, X[i]))
	
for l in event:
	if l[1] == 1:
		bisect.insort(working, l[2])
	elif l[1] == 0:
		del working[bisect.bisect(working, l[2]) - 1]
	else:
		if len(working) > 0:
			print(working[0])
		else:
			print(-1)

Submission status: Time Limit Exceeded

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

"""
import sys


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 = []
    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)
        if blocked:
            ans.append(min(blocked))
        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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jun 13 14:27:40 2019

@author: YudNK
"""
import bisect

N, Q = map(int, input().split())
X = []
for i in range(N):
    s, t, x = map(int, input().split())
    X.append([s - x, t - x, x])
D = [int(input()) for i in range(Q)]
keys = [i for i in range(Q)]
X.sort(key = lambda x:x[2])
ans = [-1]*Q
for i in X:
    m = i[0]
    n = i[1]
    xi = i[2]
    count = 0
    it = bisect.bisect_left(D, m)
    while it != len(D):
        if D[it] >= n:
            break
        ans[keys[it]] = xi
        D[it] = 0
        keys[it] = 0
        it += 1
        count += 1
    D.sort()
    D = D[count:]
    keys.sort()
    keys = keys[count:]
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jun 13 14:27:40 2019

@author: YudNK
"""
import bisect

N, Q = map(int, input().split())
X = []
for i in range(N):
    s, t, x = map(int, input().split())
    X.append([s - x, t - x, x])
D = [int(input()) for i in range(Q)]
keys = [i for i in range(Q)]
X.sort(key = lambda x:x[2])
ans = [-1]*Q
for i in X:
    m = i[0]
    n = i[1]
    xi = i[2]
    it = bisect.bisect_left(D, m)
    while it != len(D):
        if D[it] >= n:
            break
        ans[keys[it]] = xi
        D.pop(it)
        keys.pop(it)
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jun 13 14:27:40 2019

@author: YudNK
"""
import bisect

N, Q = map(int, input().split())
X = []
for i in range(N):
    s, t, x = map(int, input().split())
    X.append([s - x, t - x, x])
D = [int(input()) for i in range(Q)]
keys = [i for i in range(Q)]
X.sort(key = lambda x:x[2])
ans = [-1 for i in range(Q)]
for i in X:
    m = i[0]
    n = i[1]
    xi = i[2]
    it = bisect.bisect_left(D, m)
    while it != len(D):
        if D[it] >= n:
            break
        ans[keys[it]] = xi
        D.pop(it)
        keys.pop(it)
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jun 13 14:27:40 2019

@author: YudNK
"""
import bisect

N, Q = map(int, input().split())
X = []
for i in range(N):
    s, t, x = map(int, input().split())
    X.append([s - x, t - x, x])
D = [[i, int(input())] for i in range(Q)]
X.sort(key = lambda x:x[2])
ans = [-1 for i in range(Q)]
for i in X:
    m = i[0]
    n = i[1]
    xi = i[2]
    keys = [r[1] for r in D]
    it = bisect.bisect_left(keys, m)
    while it != len(D):
        if D[it][1] >= n:
            break
        ans[D[it][0]] = xi
        D.pop(it)
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
inf=float("inf")
Event=[(inf,inf,1)]
for i in range(N):
  s,t,x=map(int,input().split())
  Event.append((s-x,x,1))
  Event.append((t-x,x,-1))
Event.sort()
Set=set()
D=[int(input()) for i in range(Q)]
k=0
#print(Event)
for d in D:
  while Event[k][0]<=d:
    a,x,m=Event[k]
    #print(k,d,a,x,m)
    if m==1:
      Set.add(x)
    else:
      Set.remove(x)
    #print(Set)
    k+=1
  if Set:
    print(min(Set))
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]
# イベントを入れる配列 [時間, 追加or削除のフラグ, 場所or人の番号, 人のフラグ]
event=[]
for s,t,x in stx:
    event.append([s-x-0.5,True,x,False])
    event.append([t-x-0.5,False,x,False])
for i in range(q):
    event.append([d[i],False,i,True])

event.sort(key=lambda x:x[0])
# print(event)
goal=[-1 for _ in range(q)]
place=[]
# stop=[]
# nonstop=[]
for t, isHappen, x, isHuman in event:
    if isHuman:
        if len(place)>0:
            goal[x]=min(place)
        # # 2回行くことを判別できない
        # stopping=list(set(stop)-set(nonstop))
        # if len(stopping)>0:
        #     goal[x]=min(stopping)
    else:
        if isHappen:
            place.append(x)
            # stop.append(x)
        else:
            place.remove(x)
            # nonstop.append(x)
# print(goal)
for g in goal:
    print(g)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
con_stx = [list(map(int, input().split())) for _ in range(n)]
answer = []
for i in range(q):
    d = int(input())
    ans = 10**9+1
    for j in range(n):
        if con_stx[j][0] <= (d + con_stx[j][2]) and con_stx[j][1] > (d + con_stx[j][2]):
            if con_stx[j][2] < ans:
                ans = con_stx[j][2]
    if ans == 10**9+1:
        ans = -1
    answer.append(ans)
for a in answer:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq
from collections import defaultdict
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for i in range(N)]
Dlist = [int(input()) for i in range(Q)]
event = []
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: Time Limit Exceeded

Solution code:
import heapq as hq
from collections import defaultdict
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for i in range(N)]
Dlist = [int(input()) for i in range(Q)]
event = []
for s,t,x in STX:
    event += [[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: Time Limit Exceeded

Solution code:
import heapq as hq
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for i in range(N)]
Dlist = [int(input()) for i in range(Q)]
event = []
for s,t,x in STX:
    event += [[s - x, t-x, x]]
event.sort(key=lambda x:x[0])
h = []
tdic = {}
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: Time Limit Exceeded

Solution code:
import heapq as hq
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for i in range(N)]
event = []
for s,t,x in STX:
    event += [[s - x, t-x, x]]
event.sort(key=lambda x:x[0])
h = []
tdic = {}
ind = 0
for _ in range(Q):
    Di = int(input())
    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: Time Limit Exceeded

Solution code:
import sys 

def check_work(D, work_list):
    value_list = [-1]
    for work in work_list:
        start, end, X = work
        if start <= D <= end:
            value_list.append(X)
            break
    print(max(value_list))
    
def main():
    N, Q = map(int, input().split())
    work_list = []
    for n in range(N):
        S, T, X = map(int, input().split())
        work_list.append([X-T+1, X-S, X])
    work_list = sorted(work_list, key=lambda x:x[2])
    for q in range(Q):
        D = int(input())
        check_work(-D, work_list)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys 

def check_work(D, work_list):
    value_list = []
    for work in work_list:
        start, end, X = work
        if start <= D <= end:
            value_list.append(X)
    if value_list == []:
        print(-1)
    else:
        print(min(value_list))
          
def main():
    N, Q = map(int, input().split())
    work_list = []
    for n in range(N):
        S, T, X = map(int, input().split())
        work_list.append([X-T+1, X-S, X])
    for q in range(Q):
        D = int(input())
        check_work(-D, work_list)
main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 12 12:37:02 2019

@author: YudNK
"""

N, Q = map(int, input().split())
X = []
P = []
for i in range(N):
    l = [int(j) for j in input().split()]
    X.append(l)
    X.sort()
for j in range(Q):
    P.append(int(input()))

result = [-1 for i in range(Q)]
for i in range(Q):
    for s in X:
        px = s[0] - P[i]
        for d in range(s[1] - s[0]):
            if px + d == s[2]:
                result[i] = px + d
        if result[i] != -1:
            break
[print(i) for i in result]

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections

N, Q = map(int, input().split())
stoppedDict = collections.defaultdict(set)  # {d: x} dに出発すると、xで止まるという形式
for i in range(N):
    s, t, x = map(int, input().split())
    for j in range(s-x, t-x):
        stoppedDict[j].add(x)
#print(stoppedDict)


def solve(d):
    if len(stoppedDict[d]) != 0:
        return min(stoppedDict[d])
    else:
        return -1


for i in range(Q):
    d = int(input())
    print(solve(d))