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:
import bisect
N, Q = map(int, input().split())
L = []
for i in range(N):
    s, t, x = map(int, input().split())
    L.append((s-x, t-x, x))
L = sorted(L, key=lambda p:p[2], reverse=False)


D = []
for i in range(Q):
    D.append(int(input()))

DD = [-1] * len(D)
for l in L:
    left = bisect.bisect_left(D, l[0])
    right = bisect.bisect_left(D, l[1])
    if left != right:
        for j in range(left, right):
            if DD[j] == -1:
                DD[j] = l[2]

for d in DD:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N, Q = [int(c) for c in input().split()]

M = [10**10]*Q

STX = []
for n in range(N):
    s,t,x = [int(c) for c in input().split()]
    STX.append((s,t,x))

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

for s,t,x in STX:
    d_l = bisect_left(D, s-x)
    d_r = bisect_left(D[d_l:], t-x)+d_l
    for d in range(d_l, d_r):
        M[d] = min(x,M[d])

for q in range(Q):
    m = -1 if M[q] == 10**10 else M[q]
    print(m)

Submission status: Time Limit Exceeded

Solution code:
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)]
ans = [float("inf")] * Q

for j in range(N):
	for k in range(S[j] - X[j], T[j] - X[j]):
		for a in [x for x in range(Q) if k == D[x]]:
			ans[a] = min(ans[a], X[j])

for l in range(Q):
	if ans[l] == float("inf"):
		print(-1)
	else:
		print(ans[l])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import bisect


def main():
  n, q = map(int, input().split())
  terms = []
  times = []
  scores = [-1] * q

  for _ in range(n):
    s, t, x = map(int, input().split())
    terms.append((s - x, t - x, x))

  for _ in range(q):
    times.append(int(input()))

  times.sort()

  for s, t, x in terms:
    idx = max(bisect.bisect_left(times, s), 0)

    while idx < len(times) and times[idx] < t:
      if scores[idx] == -1:
        scores[idx] = x
      else:
        scores[idx] = min(x, scores[idx])

      idx += 1

  for score in scores:
    print(score)


if __name__ == '__main__':
  main()

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(N - 1):
    for j in range(i + 1, N):
        if X[i] > X[j]:
            tmp = S[i]
            S[i] = S[j]
            S[j] = tmp
            tmp = T[i]
            T[i] = T[j]
            T[j] = tmp
            tmp = X[i]
            X[i] = X[j]
            X[j] = tmp

for i in range(Q):
    for j in range(N):
        if S[j] <= D[i] and D[i] <= T[j]:
            print(X[j])
            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((-x,max(0,s-x),t-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]
info.sort()
for i in info:
	x,s,t = i[0],i[1],i[2]
	for j in range(m_time[s], m_time[t]):
		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:
from bisect import bisect_left
# 最初最後両方left 

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

q = [-1]*Q
for s, t, x in STX[::-1]:
    l = bisect_left(D, max(0, s-x))
    r = bisect_left(D, max(0, t-x))
    # print(s, t, x, l, r)
    count = r-l
    for i in range(count):
        if 0 <= q[l+i] < x:
            continue
        q[l+i] = x
    

# print(q)

for q_i in q:
    print(q_i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int, input().split())
STX = []
for i in range(N):
    S, T, X = map(int, input().split())
    STX.append([S, T, X])
STX = sorted(STX, key=lambda x:x[2], reverse=True)

out = defaultdict(lambda: -1)
for out_num, (S, T, X) in enumerate(STX):
    for i in range(max(S-X, 0), max(T-X, 1)):
        out[i] = X
for i in range(Q):
    print(out[int(input())])

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, Q = map(int, input().split())
L = []
for i in range(N):
    s, t, x = map(int, input().split())
    L.append((s-x, t-x, x))
L = sorted(L, key=lambda p:p[2], reverse=True)


D = []
for i in range(Q):
    D.append(int(input()))

DD = [-1] * len(D)
for l in L:
    left = bisect.bisect_left(D, l[0])
    right = bisect.bisect_left(D, l[1])
    if left != right:
        DD[left:right] = [l[2]] * (right - left)

for d in DD:
    print(d)

Submission status: Time Limit Exceeded

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

stop_arr = [[] 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

ans = ""
for a in ans_arr:
    ans += str(a)+"\n"

print(ans, end="")

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


N, Q = map(int, input().split(" "))
check_points = [input() for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1
b_left = bisect_left
for line in check_points:
    s, f, x = map(int, line.split(" "))
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for q in querys[left:right]:
        if q >= end:
            break
        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:
import sys
from collections import defaultdict
import heapq
INPUT = sys.stdin.readline

def SINGLE_INT(): return int(INPUT())
def MULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def MULTIPLE_INT_MAP(): return map(int, INPUT().split())
def SINGLE_FLOAT(): return float(INPUT())
def MULTIPLE_FLOAT_LIST(): return list(map(float, INPUT().split()))
def MULTIPLE_FLOAT_MAP(): return map(float, INPUT().split())
def SINGLE_STRING(): return INPUT()
def MULTIPLE_STRING(): return INPUT().split()

falsestart = defaultdict(list)

N, Q = MULTIPLE_INT_MAP()

for _ in range(N):

    s, t, x = MULTIPLE_INT_MAP()

    for i in range(s-x, t-x):
        if i > -1:
            heapq.heappush(falsestart[i], x)


for _ in range(Q):    
    start = SINGLE_INT()
    if not falsestart[start]:
        print(-1)
    else:
        print(heapq.heappop(falsestart[start]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

constructions = []
for _ in range(N):
    s, t, x = map(int, input().split())
    heapq.heappush(constructions, (x, s-x, t-x))

max_d = 0
D = [() for _ in range(Q)]
for i in range(Q):
    d = int(input())
    heapq.heappush(D, (d, i))
    D[i] = (d, i)
    max_d = max(max_d, d)

D.sort()
distance = [-1 for _ in range(Q)]
while constructions:
    x, s, t = heapq.heappop(constructions)
    if max_d < s or D[0][0] >= t:
        continue
    new_D = []
    for d, idx in D:
        if d >= s and d < t:
            distance[idx] = x
        else:
            new_D.append((d, idx))
    D = new_D
    if len(D) == 0:
        break
for d in distance:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
import numpy as np
# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())

def solve():
    s_list = []
    t_list = []
    x_list = []
    d_list = []
    n, q = map(int, input().split())
    dict_x_by_d = {}
    for i in range(n):
        s, t, x = map(int, input().split())

        s_list.append(s)
        t_list.append(t)
        x_list.append(x)
        for d in range(s-x, (t-1)-x+1):
            if d in dict_x_by_d:
                dict_x_by_d[d] = min(x, dict_x_by_d[d])
            else:
                dict_x_by_d[d] = x
    for i in range(q):
        d = int(input())
        d_list.append(d)
        if d in dict_x_by_d:
            print(dict_x_by_d[d])
        else:
            print(-1)

solve()

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 = []
workingXs = []

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)))
                workingXs.insert(bisect.bisect_left(workingXs, x), x)
            notyetKs.pop(0)
        else:
            break
    while len(workingKs)>0:
        ahx,bhx,x = workingKs[0][1]
        if bhx <= t:
            heappop(workingKs)
            workingXs.pop(bisect.bisect_left(workingXs,x))
        else:
            break

    #print(t, notyetKs,workingKs,doneKs)

    if len(workingKs)==0:
        print(-1)
    else:
        print(workingXs[0])

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from functools import *
from itertools import *
import operator as op

class Node:

    def __init__(self, s, t, x):
        self.s, self.t, self.x = s, t, x
        self.lhs = None
        self.rhs = None
        pass

    def merge(self, s, t, x):
        if self.s <= s and t <= self.t:
            return
        if s < self.s:
            if self.lhs:
                self.lhs.merge(s, min(self.s, t), x)
            else:
                self.lhs = Node(s, min(self.s, t), x)
                pass
            pass
        if t > self.t:
            if self.rhs:
                self.rhs.merge(max(self.t, s), t, x)
            else:
                self.rhs = Node(max(self.t, s), t, x)
                pass
            pass
        pass

    def getvalue(self, d):
        if self.s <= d and d < self.t:
            return self.x
        if d < self.s:
            if self.lhs:
                return self.lhs.getvalue(d)
            return -1
        if d >= self.t:
            if self.rhs:
                return self.rhs.getvalue(d)
            return -1
        assert(False)
        pass

    pass

def main():
    #n = int(input())
    n, q = map(int, input().split())
    #xs = list(map(int, input().split()))
    #xs = [ input().split() for _ in range(n) ]
    xs = [ list(map(int, input().split())) for _ in range(n) ]
    ds = [ int(input()) for _ in range(q) ]

    xs.sort(key=lambda x: x[2])
    ys = [ (max(0, s-x), t-x, x) for s, t, x in xs if t-x > 0]
    nodes = Node(*ys[0])
    for s, t, x in ys[1:]:
        nodes.merge(s, t, x)
        pass

    for d in ds:
        print(nodes.getvalue(d))
        pass

    pass


if __name__ == "__main__":
    main()
    pass

Submission status: Time Limit Exceeded

Solution code:
import bisect


N, Q = map(int, input().split(" "))
check_points = [input() for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1
b_left = bisect.bisect_left
for line in check_points:
    s, f, x = map(int, line.split(" "))
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for q in querys[left:right]:
        if q >= end:
            break
        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 = (int(_) for _ in input().split())
s = [list(int(_) for _ in input().split()) for i in range(n)]
s = [[i[0]-i[2],i[1]-i[2],i[2]] for i in s]
s = sorted(s,key = lambda x:x[2])

for i in range(q):
    x = int(input())
    for ii in range(len(s)):
        if s[ii][0] - x <= 0 and s[ii][1] - x > 0:
            print(s[ii][2])
            break
        if ii == len(s)-1:
            print(-1)

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):
    stx.append(LI())
for i in range(q):
    ds.append(SI())
# 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:
import itertools
import numpy as np
n, q = map(int, input().split())
time_list = []
for i in range(n):
  s, t, x = map(int, input().split())
  time_list.append([s-x, t-x, x])
time_arr = np.array(time_list)
for j in range(q):
  t = int(input())
  flg1 = t >= time_arr[:, 0]
  flg2 = t < time_arr[:, 1]
  if len(time_arr[flg1&flg2, 2]) == 0:
    m = -1
  else:
  	m = min(time_arr[flg1&flg2, 2])
  print(m)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = [0 for i in range(N)]
T = [0 for i in range(N)]
dictX = dict()
for i in range(N):
    S, T, X = map(int, input().split())
    if X in dictX.keys():
        dictX[X].append([S, T])
    else:
        dictX[X] = [[S, T]]
keylist = list(dictX.keys())
keylist.sort()
D = [[] for i in range(Q)]
for i in range(Q):
    inputD = int(input())
    D[i] = [i + inputD for i in keylist]
#print(dictX)
#print(D)
for i in range(Q):
    saigo = True
    for j in range(len(keylist)):
        lll = dictX[keylist[j]]
        for kobetu in lll:
            if D[i][j] >= kobetu[0] and D[i][j] < kobetu[1] and saigo:
                print(keylist[j])
                saigo = False
                break
        if not saigo:
            break
    if saigo:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
const = [list(map(int, input().split())) for _ in range(N)]
const = sorted(const, key=lambda x: x[2])
for _ in range(Q):
    d = int(input())
    for s, t, x in const:
        if s <= x+d <t:
            print(x)
            break
    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)]
ds = [int(input()) for _ in range(q)]
coords = set()
coords.add(0)
for s, t, x in stx:
    coords.add(s - x)
    coords.add(t - x)
i = 0
index = {}
position = [-1] * len(coords) + [1000000000000000]
for c in sorted(coords):
    index[c] = i
    position[i] = c
    i += 1
stop = [-1] * (len(coords) + 1)
for s, t, x in stx:
    start = index[s - x]
    end   = index[t - x]
    for i in range(start, end):
        if stop[i] == -1 or stop[i] > x:
            stop[i] = x
i = 0
for d in ds:
    while position[i + 1] <= d:
        i += 1
    print(stop[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
INPUT = sys.stdin.readline

def SINGLE_INT(): return int(INPUT())
def MULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def MULTIPLE_INT_MAP(): return map(int, INPUT().split())
def SINGLE_FLOAT(): return float(INPUT())
def MULTIPLE_FLOAT_LIST(): return list(map(float, INPUT().split()))
def MULTIPLE_FLOAT_MAP(): return map(float, INPUT().split())
def SINGLE_STRING(): return INPUT()
def MULTIPLE_STRING(): return INPUT().split()

falsestart = defaultdict(list)

N, Q = MULTIPLE_INT_MAP()

for _ in range(N):

    s, t, x = MULTIPLE_INT_MAP()

    for i in range(s-x, t-x):
        if i > -1:
            falsestart[i].append(x)


for _ in range(Q):    
    start = SINGLE_INT()
    if not falsestart[start]:
        print(-1)
    else:
        print(min(falsestart[start]))

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

ans = ""
for a in ans_arr:
    ans += str(a)+"\n"

print(ans, end="")

Submission status: Time Limit Exceeded

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

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 = [0] * Q
for i in range(Q):
    d = int(input())
    D[i] = d

ans = [-1] * Q
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:
from operator import itemgetter


def main():
    n, q = list(map(int, input().split()))
    stops = []
    for _ in range(n):
        s, t, x = list(map(int, input().split()))
        stops.append((s, t, x))
    delay = []
    for i in range(q):
        delay.append([int(input()), False, -1])

    stops = sorted(stops, key=itemgetter(2))

    for s, t, x in stops:
        for idx, item in enumerate(delay):
            d, stopped, score = item
            if not stopped:
                time_at_x = x + d
                if s - 0.5 < time_at_x < t - 0.5:
                    delay[idx][2] = x
                    delay[idx][1] = True

    for item in delay:
        print(item[2])


main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
K = ['NUL' for i in range(N)]
for i in range(N):
        K[i] = list(map(int, input().split()))
K.sort(key=lambda x: x[2]) # 通行止め座標が小さい順にソート

for i in range(Q):
        D = int(input())
        okvalue = 0
        i = 0
        while i < N and okvalue == 0:
                collision_time = D + K[i][2]
                if K[i][0] - 0.5 < collision_time < K[i][1] - 0.5:
                        okvalue = 1
                else:
                        i += 1
        
        if i < N:
                print(K[i][2])
        else:
                print(-1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N, Q = [int(c) for c in input().split()]

M = [10**10]*Q

STX = []
for n in range(N):
    s,t,x = [int(c) for c in input().split()]
    STX.append((s,t,x))

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

for s,t,x in STX:
    d_l = bisect_left(D, s-x)
    d_r = bisect_left(D, t-x)
    for d in range(d_l, d_r):
        M[d] = min(x,M[d])

for q in range(Q):
    m = -1 if M[q] == 10**10 else M[q]
    print(m)

Submission status: Time Limit Exceeded

Solution code:
import bisect


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

for line in check_points:
    s, f, x = map(int, line.split(" "))
    start = s-x
    end = f-x
    left = bisect.bisect_left(querys, start)
    right = bisect.bisect_right(querys, end)
    for q in querys[left:right]:
        if q >= end:
            break
        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:
from bisect import insort_left

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])
    insort_left(XST, (x, s, t))
    # 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 collections import defaultdict

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

dd = defaultdict(int)
for stx in stxList:
    s, t, x = stx
    for i in range(max(0, s - x), t - x):
        if dd[i] == 0:
            dd[i] = x

for d in dList:
    if dd[d] != 0:
        print(dd[d])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy
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 = numpy.array([-1]*Q)

for i in stop_arr_ind:
    s,t,x = stop_arr[i]
    q_start = numpy.searchsorted(Q_arr, s-x)
    q_stop = numpy.searchsorted(Q_arr, t-x)
    ans_arr[q_start:q_stop] = x

ans = ""
for a in ans_arr:
    ans += str(a)+"\n"

print(ans[:-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] = min(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(min(vl,vr))

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

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

DD.sort()

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    Q = int(buflist[1])
    XST = dict()
    for i in range(N):
        buf = input()
        buflist = buf.split()
        X = int(buflist[2])
        ST = (int(buflist[0]) - X, int(buflist[1]) - X)
        if X not in XST:
            XST[X] = [ST]
        else:
            XST[X].append(ST)
    Ds = set()
    Dl = []
    for i in range(Q):
        buf = input()
        D = int(buf)
        Ds.add(D)
        Dl.append(D)
    distance = []
    for i in range(Q):
        distance.append(-1)
    for i in sorted(XST):
        for x in XST[i]:
            start = bisect_left(Dl, x[0])
            point = start
            while point < Q:
                if Dl[point] >= x[1]:
                    break
                if distance[point] == -1:
                    distance[point] = i
                point += 1
    for x in distance:
        print(x)


if __name__ == '__main__':
    main()

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':
    i = bisect_left(cur, x)
    cur.pop(i)
  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:
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:
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 = s-x
    end = 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

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = [0 for i in range(N)]
T = [0 for i in range(N)]
dictX = dict()
for i in range(N):
    S, T, X = map(int, input().split())
    if X in dictX.keys():
        dictX[X].append([S, T])
    else:
        dictX[X] = [[S, T]]
keylist = list(dictX.keys())
keylist.sort()
D = [[] for i in range(Q)]
for i in range(Q):
    inputD = int(input())
    D[i] = [i + inputD for i in keylist]
#print(dictX)
#print(D)
for i in range(Q):
    saigo = True
    for j in range(len(keylist)):
        lll = dictX[keylist[j]]
        for kobetu in lll:
            if D[i][j] >= kobetu[0] and D[i][j] < kobetu[1] and saigo:
                print(keylist[j])
                saigo = False
                break
    if saigo:
        print(-1)

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 = [0] * Q
for i in range(Q):
    d = int(input())
    D[i] = d

ans = [-1] * Q
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)