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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import bisect


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    STX = []
    for s,t,x in zip(S,T,X):
        STX.append((s,t,x))

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

    R = [-1] * Q
    for stx in STX:
        ds = stx[0] - stx[2]
        de = stx[1] -1 - stx[2]
        di1 = bisect.bisect_left(D,ds)
        di2 = bisect.bisect_right(D,de)
        di2 = min(Q-1,di2)
        for i in range(di1,di2+1) :
            if ds <= D[i] <= de and R[i] < 0:
                R[i] = stx[2]

    for r in R:
        print(r)




# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]" 
    T = [int()] * (N)  # type: "List[int]" 
    X = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(N, Q, S, T, X, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
l = raw_input().split()
N = int(l[0])
Q = int(l[1])

S = []
T = []
X = []
D = []

for i in range(N):
    l = raw_input().split()
    S.append(int(l[0]))
    T.append(int(l[1]))
    X.append(int(l[2]))

for i in range(Q):
    l = raw_input().split()
    D.append(int(l[0]))

# print(N, Q, S, T, X, D)

for i in range(Q):
    started = D[i]
    stopped = -1
    # print('started, stopped', started, stopped)
    for j in range(N):
        x = X[j]
        s = S[j] - 0.5
        t = T[j] - 0.5
        arrived = started + x
        # print('x, arrived, s, t', x, arrived, s, t)
        if arrived >= s and arrived <= t:
            stopped = x
            break
    print(stopped)

Submission status: Wrong Answer

Solution code:
N,Q=(int(x) for x in input().split())
L=[]

for _ in range(N):
    S,T,X=(int(x) for x in input().split())
    L.append([S-X,T-X-1,X])#Xで引っ掛かる人で最も早いスタート,最も遅いスタート,X

L.sort(key=lambda elm:(elm[2],elm[1]))#Xの小さい順に並び変え


count=0
for _ in range(Q):
    D=int(input())
    bol=True
    for i,(s,t,x) in enumerate(L):
        if D>t:
            L=L[:i]+L[i+1:]
        elif s<=D and D<=t:
            print(x)
            bol=False
            break
    if bol:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def initialize(N):
    d = N
    k = 0
    while d > 0:
        k += 1
        d //= 2
    L = [100000000000000] * (pow(2, k+1) - 1)
    return L, k

def change(i, j, a, left, right, level, where, btree, k):  
    if j < left or i > right: return
    elif level == k:
        btree[where] = min(a, btree[where])
    elif i <= left and right <= j:
        if a < btree[where]:
            btree[where] = a
            change(i, j, a, left, (left + right)//2, level + 1, 2 * where + 1, btree, k)
            change(i, j, a, (left + right)//2, right, level + 1, 2 * where + 2, btree, k)
    else:
        change(i, j, a, left, (left + right)//2, level + 1, 2 * where + 1, btree, k)
        change(i, j, a, (left + right)//2, right, level + 1, 2 * where + 2, btree, k)

N, Q = map(int, line_input())
stop = [[int(i) for i in line_input()] for j in range(N)]
D = [int(single_input()) for i in range(Q)]
cango, k = initialize(Q)
for i in range(N):
    sleft = bisect_left(D, max(stop[i][0] - stop[i][2], 0))
    sright = bisect_left(D, max(stop[i][1] - stop[i][2], 0))
    if sleft < sright:
        change(sleft, sright-1, stop[i][2], 0, 2 ** k, 0, 0, cango, k)
for i in range(Q):
    if cango[pow(2, k) - 1 + i] == 100000000000000: print(-1)
    else: print(cango[pow(2, k) - 1 + i])

Submission status: Wrong Answer

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] < d:
        i += 1
    print(stop[i])

Submission status: Wrong Answer

Solution code:
import heapq

N, Q = map(int, input().split())
INF = 10 ** 10
ans = [INF] * Q
stops = [0] * N
times = []
for i in range(N):
    s, t, x = map(int, input().split())
    times.append((s-x, 0, i))
    times.append((t-x, -1, i))
    stops[i] = x
for i in range(Q):
    d = int(input())
    times.append((d, 1, i))

times.sort()
pque = []
used = set()
for t, k, i in times:
    #print(t, k, i)
    if k == -1:
        used.add(i)
    elif k == 0:
        heapq.heappush(pque, (stops[i], i))
    else:
        while pque:
            x, j = heapq.heappop(pque)
            if j not in used:
                ans[i] = min(ans[i], x)
                break
        else:
            ans[i] = -1
for x in ans:
    if x != INF:
        print(x)
    else:
        print(-1)

Submission status: Wrong Answer

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 ti in range(max(0,s-x), min(t-x,max_t-1)):
		if ti not in time: continue
		if time[ti]<0 or time[ti]>x:
			time[ti] = x

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import *
N, Q = map(int, input().split())

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

X = sorted(X, key = lambda x: x[2])
D = [int(input()) for _ in range(Q)]
i = 0
j = 0
A = []
B = []
C = []
for q in range(Q):
    while i < len(X) and D[q] >= X[i][0]:
        a, b, x = X[i]
        heappush(A, (x, b))
        heappush(B, (b, x))
        i += 1
    while len(B) and B[0][0] <= D[q]:
        b, x = heappop(B)
        heappush(C, (x, b))
    while len(C) and len(A) and C[0] == A[0]:
        heappop(A)
        heappop(C)
    print(A[0][0] if A else -1)

Submission status: Wrong Answer

Solution code:
import copy
N, Q = map(int, input().split())
Catch = []
for i in range(N):
    S, T, X = map(int, input().split())
    Catch.append((S, T, X))

Catch.sort()
People = [int(input()) for i in range(Q)]

i = 0
for p in People:
    remember = copy.deepcopy(i)
    while i < N:
        s, t, x = Catch[i]
        if s <= x + p < t:
            print(x)
            break
        elif x + p < s:
            i += 1
        elif x + p >= t:
            i += 1

        if i >= N:
            print(-1)
            i = remember - 1
            break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
 
 
def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    def bsearch(val, D):
        l = 0
        r = Q
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val < m:
                r = m
            else:
                l = m
        #print(val, l, r)
        return l
    a = []
    for i in range(N):
        a.append([X[i], max(0, -(X[i] - S[i])), max(0, -(X[i] - T[i]))])
    a.sort(key=lambda x: x[0])
    ret = [-1] * Q
    for tmp in a:
        l = bsearch(tmp[1], D)
        r = bsearch(tmp[2], D)
        #print(tmp)
        #print(l, r)
        for i in range(l - 1, r):
            if i >= 0 and i < Q and ret[i] < 0:
                ret[i] = tmp[0]
 
    for r in ret:
        print(r)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]" 
    T = [int()] * (N)  # type: "List[int]" 
    X = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(N, Q, S, T, X, D)
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def hersCode(L, n):
  ok = len(L) - 1
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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

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

L = [-1] * Q
for s, t, x in STX:
  l = hersCode(D, s - x)
  r = hersCode(D, t - x)
  for i in range(l, r):
    L[i] = x

for i in L:
  print(i)

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
def hersCode(L, n):
  ok = len(L) - 1
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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

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

L = [[] for _ in range(Q + 1)]
for s, t, x in STX:
  l = hersCode(D, s - x)
  r = hersCode(D, t - x)
  L[l].append(x)
  L[r].append(-x)

S = []
for i in L:
  if i != []:
    for j in i:
      if j < 0:
        S.remove(-j)
      else:
        S.append(j)
    S.sort()
  if S == []:
    print(-1)
  else:
    print(S[0])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
N, Q = map(int, input().split())
P = []
for i in range(N):
    s, t, x = map(int, input().split())
    P.append((s, t, x))

P = sorted(P)
D = []
j = 0
for i in range(Q):
    d = int(input())
    D.append(d)

ans = [-1] * Q
for j in range(N):
    s, t, x = P[j]
    k1 = bisect_left(D, s - x)
    k2 = bisect_left(D, t - x)
    for i in range(max(0, k1), min(Q, k2)):
        if ans[i] == -1:
            ans[i] = x

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.sort(key=lambda x: x[2])
for i in range(N):
    a[i] = [a[i][0] - a[i][2], a[i][1] - a[i][2], a[i][2]]
d = [int(input()) for _ in range(Q)]
idx = 0
for p in d:
    flg = 1
    while not (a[idx][0] <= p < a[idx][1]):
        if idx + 1 >= N or a[idx][1] <= p < a[idx + 1][0]:
            flg = 0
            break
        idx += 1
    print(a[idx][2] if flg else -1)

Submission status: Wrong Answer

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

	now = con
	for i, time in enumerate(now):
		cur = start + time[2]
		if time[0]-0.5<=cur<=time[1]-0.5:
			final = time[2]
			break
		elif time[1] <= start:
			now.pop(i)
	con = now
	print(final)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from bisect import bisect,bisect_left
N,Q=map(int,input().split())
table=[]
for i in range(N):
    s,t,x=map(int,input().split())
    if t-1-x<0:
        continue
    #print((max(0,s-x),t-1-x))
    table.append((x,max(0,s-x),t-1-x))
H=[]
D=[int(input()) for i in range(Q)]
#print(D)
for x,a,b in table:
    #print(x,a,b,(x,bisect_left(D,a),bisect(D,b)))
    heappush(H,(bisect_left(D,a),bisect(D,b),x))
K=[]
U=[10**12]*Q
J=[]
for i in range(Q):
    while len(J)>0 and J[0][2]<=i:
        x,a,b=heappop(J)
    while len(H)>0 and H[0][0]<=i:
        a,b,x=heappop(H)
        heappush(J,(x,a,b))
    if len(J)>0:
        U[i]=min(U[i],J[0][0])
    #print(i,J,H,U[i])
for i in range(Q):
    if U[i]==10**12:
        print(-1)
    else:
        print(U[i])

Submission status: Wrong Answer

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] > x:
            ans[i] = x
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort(key=lambda x: x[2])
d = [int(input()) for _ in range(q)]
k = 0
kk = 0
for i, di in enumerate(d):
    ans = -1
    for j in range(k, n):
        s, t, x = p[j]
        tj = x + di
        if s <= tj < t:
            ans = x
            k = kk
            break
        kk += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    def bsearch(val, D):
        l = 0
        r = Q
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val < m:
                r = m
            else:
                l = m
        #print(val, l, r)
        return l
    a = []
    for i in range(N):
        a.append([X[i], max(0, -(X[i] - S[i])), max(0, -(X[i] - T[i]))])
    a.sort(key=lambda x: x[0])
    ret = [-1] * Q
    for tmp in a:
        l = bsearch(tmp[1], D)
        r = bsearch(tmp[2], D)
        #print(tmp)
        #print(l, r)
        for i in range(l - 1, r):
            if i >= 0 and i < Q and ret[i] < 0:
                ret[i] = tmp[0]

    for r in ret:
        print(r)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]" 
    T = [int()] * (N)  # type: "List[int]" 
    X = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(N, Q, S, T, X, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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.sort(key=lambda x:x[2])

stop_arr_2 = []
sx_min = 10**10
tx_max = 0
for stx in stop_arr:
    s,t,x = stx
    if s-x < sx_min or t-x > tx_max:
        sx_min = min(sx_min, s-x)
        tx_max = max(tx_max, t-x)
        stop_arr_2.append(stx)

stop_arr = reversed(stop_arr_2)

ans_arr = [-1]*Q

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

for a in ans_arr:
    print(a)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().strip().split(' '))
dic = {}
for _ in range(n):
    s,t,x = map(int,input().strip().split(' '))
    if x not in dic.keys():
        dic[x] = [[s-0.5,t-0.5]]
    else:
        dic[x].append([s-0.5,t-0.5])
dic2 = {}
for i in sorted(dic):
    dic2[i] = dic[i]
ls = []
for _ in range(q):
    ls.append(int(input()))

for val in ls:
    f = 1
    for row in dic2.items():
        key,item = row
        p = val+key
        for value in item:
            s,e = value
            if p>=s and p<e:
                f = 0
                break
        if f==0:
            break
    if f==0:
        print(key)
    else:
        print("-1")

Submission status: Wrong Answer

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

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) ]
    xs.sort(key=lambda x: x[2])
    ds = [ int(input()) for _ in range(q) ]

    ys = [ (max(0, s-x), t-x, x) for s, t, x in xs if t-x >= 0]
    
    v, w = ys[0][0], ys[0][1]
    zs = [ys[0]]
    for s, t, x in ys[1:]:
        if s >= v and t <= w:
            pass
        else:
            zs.append((s, t, x))
            v = min(v, s)
            w = max(w, t)
            pass
        pass

    def doit(xs, d):
        for s, t, x in zs:
            if d >= s and d < t:
                return x
            pass
        return -1

    for d in ds:
        print(doit(xs, d))
        pass

    pass


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

Submission status: Wrong Answer

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))
SmXTmXX.sort()
print(SmXTmXX)
DI = []
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]
    i = bisect_left(D, di, i)
    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: Wrong Answer

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

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


S = []

for i in range(N):
    s, t, x = list(map(int, input().split()))
    S += [(s-x, 1, x), (t-x, -1, x)]

S.sort()
S += [(1e9+7, 0)]

idx = 0
cum = 0
for i in range(Q):
    D = int(input())
    while S[idx][0] <= D:
        cum += S[idx][1]
        idx += 1
    if cum == 0:
        print("-1")
    else:
        print(S[idx][2])

Submission status: Wrong Answer

Solution code:
import sys, heapq
input = sys.stdin.readline

def f(n, q):
    xst = []
    heapq.heapify(xst)
    for i in range(n):
        s, t, x = map(int, input().split())
        heapq.heappush(xst, [x, s - x, t - x])
    for i in range(q):
        d = int(input())
        for x, s, t in xst:
            if s <= d < t:
                print(x)
                break
        else:
            print(-1)

n, q = map(int, input().split())
f(n, q)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
LI = []
for _ in range(N):
    s,t,x = map(int,input().split())
    LI.append([t-x,s-x,x])
LI.sort()
K = 0
for i in range(Q):
    D = int(input())
    L = []
    for j in range(K,N):
        if LI[j][0] < D:
            K = j+1
        if (LI[j][1] <= D)&(D < LI[j][0]):
            L.append(LI[j][2])
        if D < LI[j][1]:
            break
    if L == []:
        print(-1)
    else:
        print(min(L))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N, Q = map(int, input().split())
INF = 10**10
arr = [(10**10, INF)]

for _ in range(N):
  s, t, x = map(int, input().split())
  arr.append((s*2-1-x*2, INF))
  arr.append((t*2-1-x*2, x))
arr.sort()

for _ in range(Q):
  d = int(input())
  idx = bisect_left(arr, (d*2, -1))
  print(-1 if arr[idx][1] == INF else arr[idx][1])

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().strip().split(' '))
dic = {}
for _ in range(n):
    s,t,x = map(int,input().strip().split(' '))
    if x not in dic.keys():
        dic[x] = [[s-0.5,t-0.5]]
    else:
        dic[x].append([s-0.5,t-0.5])
ls = []
for _ in range(q):
    ls.append(int(input()))

for val in ls:
    f = 1
    for row in dic.items():
        key,item = row
        p = val+key
        for value in item:
            s,e = value
            if p>=s and p<=e:
                f = 0
                break
        if f==0:
            break
    if f==0:
        print(key)
    else:
        print("-1")

Submission status: Wrong Answer

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])

print(con)

for i in range(q):
	start = int(input())

	cont = True
	for time in con:
		loc = time[2]
		cur = start + loc
		if time[0]-0.5<=cur<=time[1]-0.5:
			print(time[2])
			cont = False
			break
	if cont:
		print(-1)

Submission status: Wrong Answer

Solution code:
n,q = [int(x) for x in input().split()]   #n个块,q个人
rw = []
for i in range(n):
    rw.append([int(x) for x in input().split()])   #si,ti,xi
D = [int(input()) for i in range(q)]
ans = []
for i in range(q):
    for each in rw:
        if  each[0]-0.5 <=each[2]+D[i] < each[1]-0.5:
            ans.append(each[2])
            break
    else:
        ans.append(-1)

for each in ans:
    print(each)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return 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([max(0, S - X), X, 0, i])
    Stop.append([max(0, T - X), X, 1, i])
Stop.sort(key=itemgetter(0, 2))
q = []
notClosed = set()
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, time, idx))
    else:
        notClosed.add(idx)
        while len(q)>0 and q[0][2] in notClosed:
            aaa = heapq.heappop(q)[2]
            notClosed.remove(aaa)

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

print(A)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
D_kai=[(i,d) for i,d in enumerate(D)]
D_kai.sort(key=lambda x:x[1])
D=[d[1] for d in D_kai]
Dnum=[d[0] for d in D_kai]
kouji_kai=[(max(0,S-X),T-X-1,X) for S,T,X in kouji]
kouji_kai.sort(key=lambda x:x[2])
import bisect
ans=[-1]*Q
for b,e,x in kouji_kai:
    left=bisect.bisect_left(D,b)
    right=bisect.bisect_left(D,e)
    for idx in range(left,right):
        if ans[Dnum[idx]]==-1:
            ans[Dnum[idx]]=x
for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import collections

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for i in range(n)]
di = collections.defaultdict(list)
for i in stx:
    di[i[2]].append(i[:2])
for i in range(q):
    d = int(input())
    flag = False
    for j in di.keys():
        t = j + d
        for k in di[j]:
            if k[0] <= t < k[1]:
                flag = True
            if flag:
                break
        if flag:
            break
    if flag:
        print(j)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
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([max(0, S - X), X, 0, i])
    Stop.append([max(0, T - X), X, 1, i])
Stop.sort(key=itemgetter(0, 2))
q = []
notClosed = set()
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, time, idx))
    else:
        notClosed.add(idx)
        while len(q)>0 and q[0][2] in notClosed:
            aaa = heapq.heappop(q)[2]
            notClosed.remove(aaa)

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))

for _ in range(Q):
    D = int(input())
    idx = bisect_right(A, (D-1, 1<<60))
    if idx == len(A):
        idx-=1
    print(A[idx][1])

Submission status: Wrong Answer

Solution code:
import collections

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for i in range(n)]
di = collections.defaultdict(list)
for i in stx:
    di[i[2]].append(i[:2])
print(di)
for i in range(q):
    d = int(input())
    flag = False
    for j in di.keys():
        t = j + d
        for k in di[j]:
            if k[0] <= t < k[1]:
                flag = True
            if flag:
                break
        if flag:
            break
    if flag:
        print(j)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input =sys.stdin.readline
N,Q =map(int,input().split())
lis =[[int(i)for i in input().split()]for _ in range(N)]
D =[int(input()) for _ in range(Q)]
lis = sorted(lis,key = lambda x:-x[2])
basyo = [[0,-1,-1],[10**9+1,-1,-1]]#[start,end]
def nibun(li,x):
    def hantei(numb):
        if li[numb][0]>x:
            return True
        else:
            return False
    left = -1
    right =len(li)
    while right - left != 1:
        med = (left+right)//2
        if hantei(med):
            right = med
        else:
            left = med
    return left

for posi in lis:
    X =max(posi[0]-posi[2],0)
    ind = nibun(basyo,X)
    if basyo[ind][0]!=X:
        basyo.insert(ind+1,[X,posi[2],-1])
    else:
        basyo[ind][1]=posi[2]
    X =max(posi[1]-1-posi[2],0)
    ind =nibun(basyo,X)
    if basyo[ind][0]!=X:
        basyo.insert(ind+1,[X,-1,posi[2]])
    else:
        basyo[ind][2]=X
if basyo[0][1]==basyo[0][2]:
    basyo[0][1]=-1
print(basyo)
for i in D:
    ind =nibun(basyo,i)
    if basyo[ind][1]==-1 and i==basyo[ind][0]:
        print(basyo[ind][2])
    else:
        print(basyo[ind][1])

Submission status: Wrong Answer

Solution code:
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([max(0, S - X), X, 0, i])
    Stop.append([max(0, T - X), X, 1, i])
Stop.sort(key=itemgetter(0, 2))
q = []
notClosed = set()
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, time, idx))
    else:
        notClosed.add(idx)
        while len(q)>0 and q[0][2] in notClosed:
            heapq.heappop(q)

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))

print(A)
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A, (D-1, 1<<60))
    if idx == len(A):
        idx-=1
    print(A[idx][1])

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for n in range(N)]
D = [int(input()) for q in range(Q)]

max_X = max(map(lambda x: x[2], STX))
max_T = max(map(lambda x: x[1], STX))

prog = []
finish = [-1] * Q
next_D = 0
for i in range(max_T + 1):
    now = [l[2] for l in filter(lambda r: r[0] <= i < r[1], STX)]
    remove = []
    for p in prog:
        p[1]+=1
        if p[1] in now:
            finish[p[0]] = p[1]
            remove.append(p)
    for p in remove:
        prog.remove(p)
    if next_D != -1 and i == D[next_D]:
        prog.append([next_D, 0])
        next_D = next_D + 1 if next_D < Q-1 else -1

Submission status: Time Limit Exceeded

Solution code:
# ABC128 E
from bisect import bisect_right as br

N,Q=map(int,input().split())
closed=[]
for _ in [0]*N:
    closed.append(tuple(map(int,input().split())))
closed.sort(key=lambda x:x[2])
    
D=[-int(input()) for _ in [0]*Q][::-1]

walk=[-1]*Q
for s,t,x in closed:
    ind=br(D,x-(t-0.5))
    loop=br(D,x-(s-0.5))-ind
    for i in range(loop):
        i=ind+i
        if walk[i]!=-1:
            continue
        else:
            walk[i]=x
    if not -1 in walk:
        break
print(*walk[::-1],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# ABC128 E
from bisect import bisect_right as br

N,Q=map(int,input().split())
closed=[]
for _ in [0]*N:
    closed.append(tuple(map(int,input().split())))
closed.sort(key=lambda x:x[2])
    
D=[-int(input()) for _ in [0]*Q][::-1]

walk=[-1]*Q
for s,t,x in closed:
    ind=br(D,x-(t-0.5))
    loop=br(D,x-(s-0.5))-ind
    for i in range(loop):
        i=ind+i
        if walk[i]!=-1:
            continue
        else:
            walk[i]=x
print(*walk[::-1],sep='\n')