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:
N,Q=(int(i) for i in input().split())
kouji=[]
for i in range(N):
    kouji.append([int(i) for i in input().split()])
    
for i in range(0,N):
    kouji[i].extend([kouji[i][0]-kouji[i][2],kouji[i][1]-kouji[i][2]])
kouji=sorted(kouji,key=lambda x:x[2])
D=[]
for i in range(Q):
    D.append(int(input()))

for q in range(Q):
    l=0
    t=1
    for i in kouji:
        if i[3]<=D[q] and i[4]>=D[q]:
            print(i[2])
            t=0
            break
    if t==1:
        print(-1)

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,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:
        y,u,v=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]=J[0][0]
for i in range(Q):
    if U[i]==10**12:
        print(-1)
    else:
        print(U[i])

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
STX = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: (x[2], x[0]-x[2]))
D = sorted([(int(input()), i) for i in range(Q)], key=lambda x: x[0])
distance = [-1 for i in range(Q)]
mapping = []
for s,t,x in STX:
    mapping.append((s-x, x))
    mapping.append((t-x, x))
i = 0 #mapping
j = 0 #Q

while True:
    if (i >= 2*N or j >= Q):
        break
    d = D[j][0]
    if (d >= mapping[i][0] and d < mapping[i+1][0]):
        distance[D[j][1]] = min(distance[D[j][1]], mapping[i][1]) if distance[D[j][1]]>=0 else mapping[i][1]
        j += 1
    elif (d <= mapping[i][0]):
        j += 1
    elif (d >= mapping[i+1][0]):
        i += 2   

for i in distance:
    print(i)

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
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:
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]))
D = []
for j in range(Q):
    d = int(input())
    D.append(d)
kotae = [-1]*Q
yet = list(range(Q))
for k in kouzi:
    for h in yet:
        d = D[h]
        hehen = ((k[0]-d)/k[2],(k[1]-d)/k[2])
        if hehen[0] <=  1 and hehen[1] > 1:
            kotae[h] = k[2]
            yet.remove(h)
for K in kotae:
    print(K)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
STX = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: (x[2], x[0]-x[2]))
D = sorted([(int(input()), i) for i in range(Q)], key=lambda x: x[0])
distance = [-1 for i in range(Q)]
mapping = []
for s,t,x in STX:
    mapping.append((s-x, x))
    mapping.append((t-x, x))
i = 0 #mapping
j = 0 #Q

while True:
    if (i >= 2*N or j >= Q):
        break
    d = D[j][0]
    if (d >= mapping[i][0] and d < mapping[i+1][0]):
        distance[D[j][1]] = min(distance[D[j][1]], mapping[i][1]) if distance[D[j][1]]>=0 else mapping[i][1]
        j += 1
    elif (d <= mapping[i][0]):
        j += 1
    elif (d >= mapping[i+1][0]):
        i += 2

for i in distance:
    i

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from bisect import bisect_left
from collections import defaultdict

N, Q = map(int, input().split())
S, T, X = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), (), ())
)
D = [int(input()) for _ in range(Q)]

A = []
for s, x in zip(S, X):
    A.append(
        (
            bisect_left(
                D,
                s - x
            ),
            x,
            0
        )
    )
for t, x in zip(T, X):
    A.append(
        (
            bisect_left(
                D,
                t - x
            ),
            x,
            1
        )
    )
INF = 10**18
q = []
Z = defaultdict(int)
dp = [INF for _ in range(Q)]
i = -1
heappush(q, INF)
for j, x, y in sorted(A):
    for k in range(i + 1, j):
        dp[k] = q[0] if q[0] < INF else -1
    i = j - 1
    if y == 0:
        heappush(q, x)
    if y == 1:
        Z[x] += 1
        while Z[q[0]] > 0:
            heappop(q)
            Z[x] -= 1

for ans in dp:
    print(ans)

Submission status: Wrong Answer

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)
const_list = const_list[np.argsort(const_list[:,2])]
start = const_list[:,0] - const_list[:,2]
end = const_list[:,1] - const_list[:,2] - 1
spe = start+end
se = start*end

for _ in range(Q):
    q = int(input())
    check = q*q + se - spe
    true_index_list = np.where(check>=0)[0]
    if len(true_index_list)==0:
        print(-1)
    else:
        print(const_list[:,2][true_index_list[0]])

Submission status: Wrong Answer

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])
    else:
        print("-1")

Submission status: Wrong Answer

Solution code:
import heapq
N,Q=list(map(int,input().strip().split(' ')))

Intervals=[]
Ds=[]
start={}
end={}
dic_on=[]
for _ in range(N):
    S,T,X=list(map(int,input().strip().split(' ')))
    Intervals+=[(X,X+0.5-T,X+0.5-S)]

for _ in range(Q):
    Ds+=[int(input())]

Intervals=sorted(Intervals)
for i in range(len(Intervals)):
    X,left,right= Intervals[i]
    if left in start:
        start[left]+=[i]
    else:
        start[left]=[i]

    if right in end:
        end[right]+=[i]
    else:
        end[right]=[i]

all_points=Ds[:]

for I in Intervals:
    X,left,right=I
    all_points+=[left,right]

all_points=sorted(all_points)

ans=[]
import heapq
online={}
min_online=[]
for i in range(len(Intervals)):
    online[i]=0

for p in all_points:
    #print(min_online,p)
    if type(p)==type(0.5):
        if p in start:
            for index in start[p]:
                heapq.heappush(min_online,index)
                online[index]=1
        if p in end:
            for index in end[p]:
                online[index]=0

    else:
        x=-1
        while min_online:
            y=heapq.heappop(min_online)
            if online[y]==1:
                x=y
                heapq.heappush(min_online,x)
                break
        ans+=[x]
        if x==-1:
            print(-1)
        else:
            print(Intervals[x][0])

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 = []
# print(X)
# print(D)
for q in range(Q):
    while i < len(X) and D[q] >= X[i][0]:
        a, b, x = X[i]
        # print("a, b, x =", a, b, x)
        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][0] == A[0][0]:
        heappop(A)
        heappop(C)
    # print("A=", A)
    # print("B=", B)
    # print("C=", C)
    print(A[0][0] if A else -1)

Submission status: Wrong Answer

Solution code:
n, q = map(int,input().split())
sList = [list(map(int, input().split())) for i in range(n)]
dList = [int(input()) for i in range(q)]
sList.sort(key=lambda x: x[2])
infinite = True
for i in dList:
  for start, end, place in sList:
    if (i + place >= start) and (i + place <= end):
      print(place)
      infinite = False
      break
  if infinite == True:
    print(-1)
  else:
    infinite = True

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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())
STXlist = [list(map(int,input().split())) for _ in range(n)]
D = [(-1)*int(input()) for _ in range(q)]

time = 0
stop = 1
ans = [1j] * q
T = (sorted(STXlist, key=lambda x: x[1],reverse=True))  
Tmax = T[0][2]

while True:
    time += 1
    D = list(map(lambda x:x+1 , D))

    for STX in STXlist:
        if time >= STX[0] and time < STX[1]:
            if STX[2] in D:
                stop += 1
                ans[D.index(STX[2])] = D[D.index(STX[2])]
                D[D.index(STX[2])] = (1 + 1j)

    if stop == q:
        for i in ans:
            print(i)
        break
    
    if time > Tmax + 10:
        indexes = [i for i, x in enumerate(ans) if x == 1j]
        for i in indexes:
            ans[ans.index(1j)] = -1
        for i in ans:
            print(i)
        break

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 = [[-1, 0]] * Q
for s, t, x in STX:
  l = hersCode(D, s - x)
  r = hersCode(D, t - x)

  if L[l][1] != 0:
    k = L[l][1]
    while L[k][1] != 0:
      k = L[k][1]
  else:
    k = l
  for i in range(k, r):
    L[i] = [x, r]

for i in L:
  print(i[0])

Submission status: Wrong Answer

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

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: 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,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:
        y,u,v=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
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import bisect

n,q = na()
xx = []
ss =[]

for i in range(n):
  s,t,x = na()
  xx.append([s-0.5-x,t-0.5-x,x])
  ss.append(s-0.5-x)

xx.sort()
ss.sort()
ans = []

for i in range(q):
  d = ni()
  a = 10000000000000
  b = bisect.bisect_left(ss,d)
  for j in range(max(0,b-3),n):
      if xx[j][0] < d and d < xx[j][1]:
          a = min(xx[j][2],a)
      if xx[j][0] > d:
          break
  if a == 10000000000000:
      a=-1
  ans.append(a)

for i in ans:
  print(i)

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,x,s-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][2] <= D)&(D < LI[j][0]):
            print(LI[j][1])
            L.append(LI[j][1])
        if D < LI[j][2]:
            break
    if L == []:
        print(-1)

Submission status: Wrong Answer

Solution code:
import bisect

n, q = list(map(int, input().split(" ")))
N = 4 * n
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) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 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

# 区間[l, r)をxで更新
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])

# 区間[l, r)内の最小値を求める
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


conditions = []
for i in range(n):
    s, t, x = list(map(int, input().split(" ")))
    conditions.append((s - x, t - x, x))

queries = []
for _ in range(q):
    queries.append(int(input()))

coordinates = []
for s, t, x in conditions:
    coordinates.append(s - 1)
    coordinates.append(s)
    coordinates.append(t)
    coordinates.append(t + 1)

coordinates = list(set(coordinates))
coordinates.sort()

coord_dict = {}
for i, coord in enumerate(coordinates):
    coord_dict[coord] = i

for s, t, x in conditions:
    update(coord_dict[s], coord_dict[t], x)

for i in queries:

    idx = bisect.bisect_right(coordinates, i) - 1
    # print(coordinates, i, idx)
    ans = query(idx, idx + 1)
    if idx == - 1 or ans == INF:
        print(-1)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,Q = map(int,input().split())
STX = list()
for i in range(N):
    s,t,x = map(int,input().split())
    STX.append((x,s,t))
index = 0
for i in range(Q):
    d = int(input())
    bool = True
    for j in range(index,N):
        x,s,t = STX[j]
        if s<=d+x<t:
            index = j
            print(x)
            bool = False
            break
    if bool:
        print(-1)

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,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:
        y,u,v=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:
#!/usr/bin/env python3


def solv(n, q, stxs, ds):
    stxs = list(sorted(stxs, key=lambda x: x[2]))
    ans = []

    for i in range(q):
        d = -1
        t_offset = ds[i]
        for stx in stxs:
            t = t_offset + stx[2]
            if stx[0] <= t and t <= stx[1]:
                d = stx[2]
                break
        ans.append(str(d))
    return "\n".join(ans)



if __name__ == '__main__':

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

    stxs = []
    for _ in range(n):
        stxs.append(list(map(int, input().split())))
    ds = []
    for _ in range(q):
        ds.append(int(input()))

    ans = solv(n, q, stxs, ds)
    print(ans)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
w=[]
for i in range(n):
    w.append([int(i) for i in input().split()])
w=sorted(w,key=lambda x : x[0])
for i in range(q):
    d=int(input())
    for j in w:
        if j[0]<=d+j[2]<=j[1]:
            print(j[2])
            break
    else:
        print(-1)

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 = []
# print(X)
# print(D)
for q in range(Q):
    while i < len(X) and D[q] >= X[i][0]:
        a, b, x = X[i]
        # print("a, b, x =", a, b, x)
        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][0] == A[0][0]:
        heappop(A)
        heappop(C)
    # print("A=", A)
    # print("B=", B)
    # print("C=", C)
    print(A[0][0] if A else -1)

Submission status: Wrong Answer

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

def main():
    n, q = map(int, input().split())
    dic_k = defaultdict(int)
    dic = defaultdict(list)
    stxs = [list(map(int, input().split())) for i in range(n)]
    stxs.sort(key=lambda x:x[2])

    for s, t, x in stxs:
        left = max(0, s - x)
        right = max(0, t - x)

        for i in range(left // 1000, 1 + right // 1000):
            dic_k[i] = 1
        for i in range(left % 1000, right % 1000):
            dic[i] += [[i // 1000, x]]

    ds = [int(input()) for _ in range(q)]

    for d in ds:
        if d // 1000 not in dic_k:
            print(-1)
            continue
        data = dic[d % 1000]
        for dd, x in data:
            if d // 1000 == dd:
                print(x)
                break
        else:
            print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,q = LI()
    l = LIR(n)
    l.sort(key = lambda x:(x[2],x[0]-x[2]))
    ans = deque()
    for i in range(n):
        s,t,x = l[i]
        ans.append((s-x,t-x,x))
    ra = ans.popleft()
    for _ in range(q):
        d = I()
        while ans:
            if d < ra[0]:
                print(-1)
                break
            elif d < ra[1]:
                print(ra[2])
                break
            else:
                ra = ans.popleft()
                if d < ra[0]:
                    print(-1)
                    ans.appendleft(ra)
                    break
                elif d < ra[1]:
                    print(ra[2])
                    break
        else:
            print(-1)
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
n,q = map(int, input().split())
STXlist = [list(map(int,input().split())) for _ in range(n)]
D = [(-1)*int(input()) for _ in range(q)]

time = 0
stop = 1
ans = [1j] * q
T = (sorted(STXlist, key=lambda x: x[1],reverse=True))  
Tmax = T[0][2]
print(Tmax)

while True:
    time += 1
    D = list(map(lambda x:x+1 , D))

    for STX in STXlist:
        if time >= STX[0] and time < STX[1]:
            if STX[2] in D:
                stop += 1
                ans[D.index(STX[2])] = D[D.index(STX[2])]
                D[D.index(STX[2])] = (1 + 1j)
                print(STX)

    print(D)
    if stop == q:
        for i in ans:
            print(i)
        break
    
    if time > Tmax + 10:
        indexes = [i for i, x in enumerate(ans) if x == 1j]
        for i in indexes:
            ans[ans.index(1j)] = -1
        for i in ans:
            print(i)
        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_l(val, D):
        l = -1
        r = Q - 1
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val > m:
                l = m
            else:
                r = m
        #print(val, l, r)
        return r
    def bsearch_r(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_l(tmp[1], D)
        r = bsearch_r(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:
# coding:utf-8
# DDDDDDDDDDDDD

import math
import re

def main(params):
    n,q = params[0]
    ss = params[1:n+1]
    d = [int(i) for i in params[n+1:]]
    ng = []
    for i in d:
        infinite = True
        for j in ss:
            s,t,x = [int(k) for k in j.split()]
            if s - x <= i and t - x > i:
                print x
                infinite = False
                break
        if infinite == True:
            print -1

if __name__ == "__main__":
    n,q = [int(i) for i in raw_input().split()]
    cnt = n + q # TODO: edit here
    params = [[n,q]]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

Submission status: Wrong Answer

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:
            break
    else:
        print(-1)

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]))
D = []
for j in range(Q):
    d = int(input())
    D.append(d)
kotae = [-1]*Q
yet = list(range(Q))
for k in kouzi:
    hehen = [((k[0]-d)/k[2],(k[1]-d)/k[2]) for d in D]
    for h in yet:
        if hehen[h][0] <=  1 and hehen[h][1] > 1:
            kotae[h] = k[2]
            yet.remove(h)
for K in kotae:
    print(K)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys

fin = sys.stdin.readline

n, q = map(int, fin().split())
stx = [tuple(map(int, fin().split())) for _ in range(n)]
d = [int(fin()) for _ in range(q)]

new_st = [(val[0] - val[2], val[1] - val[2], val[2]) for val in stx]
new_st = sorted(new_st, key=lambda x: x[2])
dist = []

count = 0
for d_ in d:
    for i in range(count, len(new_st)):
        s, t, x = new_st[i]
        if s <= d_ < t:
            dist.append(x)
            count = i
            break
    else:
        dist.append(-1)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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)