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())
stx = [list(map(int, input().split())) for _ in range(n)]
dep_time = [int(input()) for _ in range(q)]

max_t = dep_time[-1]+1
time = {dep_t:-1 for dep_t in dep_time}

for i in range(n):
	s, t, x = stx[i]
	for dep_t in time:
		if s-x <= dep_t and dep_t < t-x:
			if time[dep_t]<0 or time[dep_t] > x:
				time[dep_t] = x

for dep_t in dep_time:
	print(time[dep_t])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right, insort_left
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

n, q = map(int, input().split())
range_dict = {}
lefts = []
rights = []
for nn in range(n):
  s, t, x = map(int, input().split())
  left = s - 0.5 - x
  right = t - 0.5 - x
  lefts.append((left, x, 'left'))
  rights.append((right, x, 'right'))
  range_dict[nn + 1] = (left, right, nn+1, x)

#print(range_dict)

ds = [int(input()) for qq in range(q)]
#for d in ds:
#  out = -1
#  for s,t,i,x in sorted(range_dict.values(), key=lambda x: x[3]):
#    if d >= s and d < t:
#      out = x
#      break
#  print(d, out)
#print(lefts)
#print(rights)
borders = sorted(lefts + rights, key=lambda x: x[0])
#print(borders)
border_dict = {}

cur_x = 10**18
cur = []

for val, x, lr in borders:
  if lr == 'left':
    insort_left(cur, x)
  elif lr == 'right':
    cur.remove(x)
  if cur:
    border_dict[val] = cur[0]
  else:
    border_dict[val] = -1
#print(border_dict)

borders = sorted(border_dict.keys())
#print(borders)
for d in ds:
  out = -1
  try:
    b = find_le(borders, d)
    out = border_dict[b]
  except ValueError:
    print('error')
    out = -1
  print(out)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, Q = [int(x) for x in input().split()]
STX = np.zeros((N, 3))
for i in range(N):
    STX[i, 0], STX[i, 1], STX[i, 2] = [int(x) for x in input().split()]
D = [int(input()) for _ in range(Q)]
dist_list = []

for d in D:
    STX_copy = np.copy(STX)
    STX_copy[:, :2] = STX_copy[:, :2] - d
    STX_copy = STX_copy[np.argsort(STX_copy[:, 2])]
    try:
        print(int(STX_copy[np.where((STX_copy[:, 0] - 0.5 <= STX_copy[:, 2]) & (STX_copy[:, 1] - 0.5 >= STX_copy[:, 2]))][0, 2]))
    except:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, Q= map(int,input().split())
const_list = []
for _ in range(N):
    const_list.append(list(map(int,input().split())))

const_list = np.array(const_list)
x_pos = np.argsort(const_list[:,2])
const_list = const_list[x_pos]
start = const_list[:,0] - const_list[:,2]
end = const_list[:,1] - const_list[:,2] - 1


for _ in range(Q):
    q = int(input())
    check = (q-start) * (end-q)
    true_index_list = np.where(check>=0)[0]
    if len(true_index_list)==0:
        print(-1)
    else:
        # stop_pos_list = [x_pos[x] for x in true_index[0]]
        print(const_list[:,2][true_index_list[0]])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
stx = [map(int, input().split()) for _ in range(n)]
d = [int(input()) for _ in range(q)]

dome = []
for s, t, x in stx:
    dome.append((x, s - x, t - x))

dome.sort()

for di in d:
    for x, ss, tt in dome:
        if ss <= di < tt:
            print(x)
            break
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
time = [0]
m_time = {}
m_time_inv = {}
time_info = []
info = []
for i in range(N):
	s,t,x = map(int,input().split())
	if t-x <= 0:
		continue
	time.append(t-x)
	time.append(max(0, s-x))
	info.append((max(0,s-x),t-x,x))
time = sorted(list(set(time)))
for i in range(len(time)):
	m_time[time[i]] = i
	m_time_inv[i] = time[i]
time_info = [-1 for i in time]
for i in info:
	s,t,x = i[0],i[1],i[2]
	for j in range(m_time[s], m_time[t]):
		if time_info[j] == -1:
			time_info[j] = x
		else:
			time_info[j] = min(time_info[j], x)

def search(t):
	l,r = 0,len(time)
	while r-l > 1:
		p = (l+r)//2
		if t >= time[p]:
			l = p
		else:
			r = p
	return l

for q in range(Q):
	t = int(input())
	print(time_info[search(t)])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split());stx = [[int(v) for v in input().split()] for _ in range(N) ];d = [int(input()) for _ in range(Q)]
stx = sorted(stx, key=lambda x:x[2])
for one in d:
    flag=True
    for k in stx:
        if k[2]+one<k[1]-0.5 and k[0]-0.5<k[2]+one:
            print(k[2]);flag=False
            break
    if flag:
      print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

#iの値をxに更新
def update(i,x):
	i += NN - 1
	SegTree[i] = x
	while i>0:
		i = (i-1)//2
		SegTree[i] = process(SegTree[i*2+1],SegTree[i*2+2])

#[A,B)の値, 呼ぶときはquery(a,b,0,0,NN)
def query(a,b,k,l,r):
	if r <= a or b <= l: #完全に含まない
		return INF
	elif a <= l and r <= b : #完全に含む
		return SegTree[k]
	else: #交差する
		vl = query(a,b,k*2+1,l,(l+r)//2)
		vr = query(a,b,k*2+2,(l+r)//2,r)
		return(process(vl,vr))

#x,yが子の時，親に返る値
def process(x,y):
	return min(x,y)


N,Q = inpl()
STX = [inpl() for i in range(N)]
DD = [[-int(input()),1,i] for i in range(Q)]

zaatu = defaultdict(int)
for i,[S,T,X] in enumerate(STX):
    l = X - (T-0.5)
    r = X - (S-0.5)
    DD.append([l,3,X])
    DD.append([r,2,X])
    zaatu[X] = i

DD.sort()

NN = 1
while NN < N:
	NN *= 2
SegTree = [INF]*(NN*2-1)

ans = [0]*Q
for k,q,x in DD:
    if q == 1:
        ans[x] = SegTree[0]
    elif q == 3:
        update(zaatu[x],x)
    elif q == 2:
        update(zaatu[x],INF)

for a in ans:
    if a == INF:
        print(-1)
    else:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
XST, D = [], []
# D = []
DMAX = 10 ** 9
# STOP = [DMAX for _ in range(10 ** 9)]
for _ in range(N):
    s, t, x = map(int, input().split())
    # a, b = max(0, s-x), min(10 ** 9, t-x)
    # for i in range(a, b):
        # STOP[i] = min(x, STOP[i])
    XST.append((x, s, t))

for _ in range(Q):
    D.append(int(input()))

XST.sort()

def stop(x, s, t, d):
    arv = d + x
    if s <= arv < t:
        return 1
    elif arv >= t:
        return 2
    return 0

    

# def stoppable(x, s, t):


for d in D:
    go = -1
    for xst in XST[:]:
        res = stop(xst[0], xst[1], xst[2], d)
        if res == 1:
            go = xst[0]
            break
        elif res == 2:
            XST.remove(xst)
    print(go)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
M, Q = map(int, input().split())
S=[0 for i in range(M)]
T=[0 for i in range(M)]
X=[0 for i in range(M)]
for i in range(M):
    S[i],T[i],X[i]=map(int,input().split())
    S[i]-=X[i];T[i]-=X[i]
D=[int(input()) for i in range(Q)]
TimeList=set()
for i in range(M):
    TimeList.add(S[i])
    TimeList.add(T[i])
for i in range(Q):
    TimeList.add(D[i])
TimeList=sorted(list(TimeList))
N=len(TimeList)
INF = 10**9+10
 
LV = (N-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)
 
def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1
 
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None
 
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
 
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])
 
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
CList=sorted([(S[i],T[i],X[i]) for i in range(M)],key=lambda x:x[2],reverse=True)
for i in range(M):
    s,t,x=CList[i]
    l=bisect_left(TimeList,s)
    r=bisect_left(TimeList,t)
    update(l,r,x)
for i in range(Q):
    k=bisect_left(TimeList,D[i])
    ans=query(k,k+1)
    if ans==INF:
        print(-1)
    else:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def get_block(const_plans, t):
    block = []
    for const_plan in const_plans:
        if const_plan[0] - 1 <= t <= const_plan[1] - 2:
            block.append(const_plan[2])
    return block

N, Q = map(int, input().split())
const_plans = []
dep_times = []
agents_loc = [0 for _ in range(Q)]
agents_v = [1 for _ in range(Q)]
t = 0
max_x = 0
max_t = 0

for _ in range(N):
    const_plan = [int(e) for e in input().split()]
    const_plans.append(const_plan[:])
    if max_x < const_plan[-1]:
        max_x = const_plan[-1]
    if max_t < const_plan[1]:
        max_t = const_plan[1]
    
for _ in range(Q):
    dep_times.append(int(input()))

while t < max_x + max_t + 1:
    block = get_block(const_plans, t)
    
    for n in range(Q):
        agents_loc[n] += agents_v[n] * min(1, max(0, t + 1 - dep_times[n]))
        if agents_v[n] != 0 and agents_loc[n] in block:
            agents_v[n] = 0
        
    t += 1

for n in range(Q):
    if agents_v[n] != 0:
        agents_loc[n] = -1
    print(agents_loc[n])

Submission status: Time Limit Exceeded

Solution code:
import bisect
from  heapq import *

kl, ql = tuple(map(int,input().split()))

ks = []
for ki in range(kl):
    a,b,x = tuple(map(int,input().split()))
    #a..b-1 nioite x ha tuukou dome
    ahx, bhx = a-x, b-x
    ks.append((ahx,bhx,x))

ds = []
for qi in range(ql):
    d = int(input())
    ds.append(d)


notyetKs = sorted(ks, key=lambda k:k[0])
workingKs = []

for t in ds:
    while len(notyetKs)>0:
        ahx,bhx,x = notyetKs[0]
        if ahx <= t:
            if t < bhx:
                heappush(workingKs,(bhx,(ahx,bhx,x)))
            notyetKs.pop(0)
        else:
            break
    while len(workingKs)>0:
        ahx,bhx,x = workingKs[0][1]
        if bhx <= t:
            heappop(workingKs)
        else:
            break

    #print(t, notyetKs,workingKs,doneKs)

    if len(workingKs)==0:
        print(-1)
    else:
        print(min(workingKs, key=lambda k:k[1][2])[1][2])

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, q = map(int, input().split())

ran = []
for i in range(n):
    s, t, x = map(int, input().split())
    ran.append((s-x, t-x-1, x))
ran.sort(key=lambda a: a[2])

qu = []
convert = {}
for i in range(q):
    que = int(input())
    convert[que] = i
    qu.append(que)
qu.sort()

memo = [-1] * q

ans = [-1] * q

for i in range(n):
    x = ran[i][2]
    l = ran[i][0]
    r = ran[i][1]
    ql = bisect.bisect_left(qu, l)
    qr = bisect.bisect_right(qu, r)
    if ql >= qr:
        continue
    while ql < qr:
        if memo[ql] >= 0:
            ql = memo[ql]
        else:
            memo[ql] = qr
            ans[convert[qu[ql]]] = x
            ql += 1

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N,Q = inpl()
STX = [inpl() for i in range(N)]
DD = [[-int(input()),1,i] for i in range(Q)]

zaatu = defaultdict(int)
for i,[S,T,X] in enumerate(STX):
    l = X - (T-0.5)
    r = X - (S-0.5)
    DD.append([l,3,X])
    DD.append([r,2,X])
    zaatu[X] = i

DD.sort()

li = [INF] * N

ans = [0]*Q
for k,q,x in DD:
    if q == 1:
        ans[x] = min(li)
    elif q == 3:
        li[zaatu[x]] = x
    elif q == 2:
        li[zaatu[x]] = INF

for a in ans:
    if a == INF:
        print(-1)
    else:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
import bisect


N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1

for s, f, x in check_points:
    start, end = (s-x, f-x)
    left = bisect.bisect_left(querys, start)
    for q in querys[left:]:
        if q >= end:
            break
        if time[q] == -1 or time[q] > x:
            time[q] = x
            continue

for q in querys:
    print(time[q])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
A,B,X,T=[0]*N,[0]*N,[0]*N,[0]*N
inf=10**9+1
for i in range(N):
	a,b,x=map(int,input().split())
	A[i]=a
	B[i]=b
	X[i]=x
for i in range(Q):
	D = [int(input())] * N
	G = []
	H = []
	for j in range(N):
		if (A[j]-X[j])<=D[j]<=(B[j]-X[j]-1):
			G.append(X[j]+D[j])
			H.append(X[j]+D[j])
		else:
			G.append(0)
			H.append(inf)
	if sum(G)==0:
		print(-1)
	else:
		print(X[H.index(min(H))])

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(n) for n in input().split()]
S, T, X = [], [], []
for _ in range(N):
    inp = [int(n) for n in input().split()]
    S.append(inp[0] - inp[2])
    T.append(inp[1] - 1 - inp[2])
    X.append(inp[2])
D = [int(input()) for _ in range(Q)]

for i in range(Q):
    x = -1
    for j in range(N):
        if S[j] <= D[i] and D[i] <= T[j]:
            if x == -1 or X[j] < x:
                x = X[j]
    print(x)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
kouzi = []
for i in range(N):
    s,t,x = map(int,input().split())
    kouzi.append([s,t,x])
kouzi = sorted(kouzi, key=lambda x:(x[2]),reverse = True)
D = []
for j in range(Q):
    d = int(input())
    D.append(d)
kotae = [-1]*Q
for k in kouzi:
    hehen = [((k[0]-d)/k[2],(k[1]-d)/k[2]) for d in D]
    for h in range(len(hehen)):
        if hehen[h][0] <=  1 and hehen[h][1] > 1:
            kotae[h] = k[2]
for K in kotae:
    print(K)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import sys
readline = sys.stdin.readline
write = sys.stdout.write
M, Q = map(int, input().split())
S=[0 for i in range(M)]
T=[0 for i in range(M)]
X=[0 for i in range(M)]
for i in range(M):
    S[i],T[i],X[i]=map(int,input().split())
    S[i]-=X[i];T[i]-=X[i]
D=[int(input()) for i in range(Q)]
TimeList=set()
for i in range(M):
    TimeList.add(S[i])
    TimeList.add(T[i])
for i in range(Q):
    TimeList.add(D[i])
TimeList=sorted(list(TimeList))
N=len(TimeList)
#print(TimeList)
INF = 2**31-1
 
LV = (N-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)
 
def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1
 
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None
 
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
 
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])
 
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
#print(S,T)
CList=sorted([(S[i],T[i],X[i]) for i in range(M)],key=lambda x:x[2],reverse=True)
for i in range(M):
    s,t,x=CList[i]
    l=bisect_left(TimeList,s)
    r=bisect_left(TimeList,t)
    #print(s,t,l,r)
    update(l,r,x)
    #print([query(i,i+1) for i in range(N)])
for i in range(Q):
    k=bisect_left(TimeList,D[i])
    ans=query(k,k+1)
    if ans==INF:
        print(-1)
    else:
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([S - X, X, 0, i])
    Stop.append([T - X, X, 1, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False]*N
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, time, idx))
    else:
        notClosed[idx] = True
        while len(q)>0 and notClosed[q[0][2]]:
            aaa = heapq.heappop(q)[2]

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
assert len(q)==0
A0 = list(map(itemgetter(0), A))
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A0, D)

    print(A[idx-1][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)]

#print(N, Q)
#print(STX)
#print(D)

for d in D:
  mindist = 10 ** 9
  for x in STX:
    if x[0] < x[2] + d + 0.5 < x[1]:
      if x[2] < mindist:
        mindist = x[2]
  if mindist == 10 ** 9:
    print(-1)
  else:
    print(mindist)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

#iの値をxに更新
def update(i,x):
	i += NN - 1
	SegTree[i] = x
	while i>0:
		i = (i-1)//2
		SegTree[i] = process(SegTree[i*2+1],SegTree[i*2+2])

#[A,B)の値, 呼ぶときはquery(a,b,0,0,NN)
def query(a,b,k,l,r):
	if r <= a or b <= l: #完全に含まない
		return INF
	elif a <= l and r <= b : #完全に含む
		return SegTree[k]
	else: #交差する
		vl = query(a,b,k*2+1,l,(l+r)//2)
		vr = query(a,b,k*2+2,(l+r)//2,r)
		return(process(vl,vr))

#x,yが子の時，親に返る値
def process(x,y):
	return min(x,y)


N,Q = inpl()
STX = [inpl() for i in range(N)]
DD = [[-int(input()),1,i] for i in range(Q)]

zaatu = defaultdict(int)
for i,[S,T,X] in enumerate(STX):
    l = X - (T-0.5)
    r = X - (S-0.5)
    DD.append([l,3,X])
    DD.append([r,2,X])
    zaatu[X] = i

DD.sort()

NN = 1
while NN < N:
	NN *= 2
SegTree = [INF]*(NN*2-1)

ans = [0]*Q
for k,q,x in DD:
    if q == 1:
        ans[x] = query(0,NN,0,0,NN)
    elif q == 3:
        update(zaatu[x],x)
    elif q == 2:
        update(zaatu[x],INF)

for a in ans:
    if a == INF:
        print(-1)
    else:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,Q = (int(x) for x in input().split())

stop_arr = [(0,0,0) for _ in range(N)]
for i in range(N):
    S,T,X = (int(x) for x in input().split())
    stop_arr[i] = (S,T,X)
Q_arr = [0 for _ in range(Q)]
for i in range(Q):
    Q_arr[i] = int(input())

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

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)
    for i in range(q_start, q_stop):
        ans_arr[i] = x

for a in ans_arr:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n,q=[int(_) for _ in input().split()]
l=[]
for iii in range(n):
  s,t,x=[int(_) for _ in input().split()]
  l.append([s,t,x])
l.sort(key=lambda x:x[2])
out=[]

for iii in range(q):
  d=int(input())
  flag=0
  for jjj in range(n):
    a=l[jjj]
    b=d+a[2]+1
    if b>a[0]-0.5 and b<a[1]+0.5:
      out.append(int(b-d-1))
      flag=1
      break
  if flag==0:
    out.append(-1)
for iii in range(q):
  print(out[iii])

Submission status: Time Limit Exceeded

Solution code:
import sys
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 int(input())
from collections import defaultdict
import bisect

n, q = LI()
ds = []
stx = []
ans = [-1 for i in range(q)]
for i in range(n):
    s, t, x = LI()
    stx.append((s, t, x))
for i in range(q):
    d = SI()
    ds.append(d)
# stx = sorted(stx, key=lambda x: x[2])
for s, t, x in stx:
    sx = s - x
    tx = t - x
    i1 = bisect.bisect_left(ds, sx)
    i2 = bisect.bisect_left(ds, tx)
    for i in range(i1, i2):
        if (ans[i] == -1) or (ans[i] > x):
            ans[i] = x
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

con = []
for i in range(n):
	con.append(list(map(int, input().split())))
con = sorted(con, key=lambda x: x[2])

for i in range(q):
	start = int(input())
	final = -1
	to_pop = []
	for i, time in enumerate(con):
		cur = start + time[2]
		if time[0]-0.5<=cur<=time[1]-0.5:
			final = time[2]
			break
		elif time[1] <= start:
			to_pop.append(i)

	for i in reversed(to_pop):
		con.pop(i)
	print(final)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N, Q = map(int, input().split())
SmXTmXX = []
for _ in range(N):
    s, t, x = map(int, input().split())
    SmXTmXX.append((s - x, t - x, x))
# print(SmXTmXX)
D = []
for i in range(Q):
    d = int(input())
    D.append(d)

ans = [-1] * Q
i = 0
for n in range(N):
    di, dj, x = SmXTmXX[n]
    if dj <= 0:
        continue
    i = bisect_left(D, di) if di > 0 else 0
    j = bisect_left(D, dj, i)
#     print(f"{i} to {j} is out")
    for k in range(i, j):
        ans[k] = x if ans[k] == -1 else min(ans[k], x)
        # print(f"marked {k} as {x}")
for v in ans:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
import bisect


N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for i in range(Q)]
time = {}
for q in querys:
    time[q] = -1

for s, f, x in check_points:
    start, end = [s-x, f-x]
    left = bisect.bisect_left(querys, start)
    right = bisect.bisect_left(querys, end)
    for q in querys[left:right]:
        if time[q] == -1 or time[q] > x:
            time[q] = x


for q in querys:
    print(time[q])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

cond = {}
for _ in range(N):
    s, t, x = map(int, input().split())
    if x not in cond.keys():
        cond[x] = [[s-x, t-x]]
    else:
        cond[x].append([s-x, t-x])
cond = sorted(cond.items(), key=lambda x:x[0], reverse=False)

def walk(d):
    for x,cs in cond:
        flg = True
        for c in cs:
            s, t = c
            if d < s or t <= d:
                pass
            else:
                flg = False
                break
        if not flg:
            return x
    return -1


D = [int(input()) for _ in range(Q)]
for d in D:
    print(walk(d))

Submission status: Time Limit Exceeded

Solution code:
class Node:

    def __init__(self, start, end):
        self.start, self.end, self.mid = start, end, (start + end) // 2
        self.val = float('inf')
        self.left = self.right = None


class NumArray:

    def __init__(self, x):
        x.sort()
        self.x_i = {v: i for i, v in enumerate(x)}
        def createTree(l, r):
            if l >= r:
                return None
            root = Node(l, r)
            if l + 1 == r:
                return root
            mid = root.mid
            root.left = createTree(l, mid)
            root.right = createTree(mid, r)
            return root
        self.root = createTree(0, len(x) - 1)

    def update(self, x1, x2, val):
        def updateVal(root, i, j):
            if root.start == i and root.end == j:
                root.val = min(root.val, val)
            else:
                mid = root.mid
                if i < mid:
                    updateVal(root.left, i, min(mid, j))
                if mid < j:
                    updateVal(root.right, max(mid, i), j)
        return updateVal(self.root, self.x_i[x1], self.x_i[x2])

    def query(self, x):
        def queryVal(root, i):
            if not root or i < root.start or i >= root.end:
                return float('inf')
            else:
                return min(root.val, queryVal(root.left, i), queryVal(root.right, i))
        return queryVal(self.root, self.x_i[x])

def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    N, Q = read_int_array()
    coords = {10**10, -10**10}
    updates = []
    for i in range(N):
        S, T, X = read_int_array()
        start, end = S-X, T-X
        coords.add(start)
        coords.add(end)
        coords.add(end)
        updates.append((start, end, X))

    ppl = []
    for i in range(Q):
        x = read_int()
        ppl.append(x)
        coords.add(x)

    st = NumArray(list(coords))
    for s, e, x in updates:
        st.update(s, e, x)
    for x in ppl:
        ans = st.query(x)
        write(ans if ans < float('inf') else -1)

main()

Submission status: Time Limit Exceeded

Solution code:
inputa = list(map(int, input().split()))
inputb = []
for i in range(inputa[0]):
  inputb.append(list(map(int, input().split())))
#座標、開始時間の順にソート
inputb.sort(key=lambda x:(x[2],x[0]))
#歩く人の処理
for i in range(inputa[1]):
  inputc = int(input())
  time = 0 + inputc
  walk = 0
  broken = 0
  #工事の気配あるとこまで歩く
  for j in range(inputa[0]):
    walk = inputb[j][2]
    time = inputc + inputb[j][2]
    if (time >= inputb[j][0]) and (time < inputb[j][1]):
      print(walk)
      broken = 1
      break
  if broken == 0:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
import operator

N, Q = map(int, sys.stdin.readline().rstrip().split(" "))
stops = []
for _ in range(N):
    S, T, X = map(int, sys.stdin.readline().rstrip().split(" "))
    stops.append((S-X, T-X-1, X))
stops.sort(key=operator.itemgetter(0))


pedestrians = []
for i in range(Q):
    D, = map(int, sys.stdin.readline().rstrip().split(" "))
    pedestrians.append((i, D))
pedestrians.sort(key=operator.itemgetter(1))

current_stops = []
# current_pedestrian = pedestrians.pop(0)

results = []
for i, current_pedestrian in pedestrians:
    while True:
        if len(stops) > 0 and stops[0][0] <= current_pedestrian:
            current_stops.append(stops.pop(0))
        else:
            break
    current_stops = [stop for stop in current_stops if stop[1] >= current_pedestrian]

    if len(current_stops) > 0:
        stop = min(current_stops, key=operator.itemgetter(2))
        # print(current_stops)
        # print(current_pedestrian, stop[2])
        results.append((i, stop[2]))
    else:
        results.append((i, -1))
for i, result in sorted(results, key=operator.itemgetter(0)):
    print(result)

exit(0)