Problem:


Score : 500 points

Problem Statement

There is an infinitely long street that runs west to east, which we consider as a number line.

There are N roadworks scheduled on this street.
The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.

Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the Q people will walk.

Constraints

All values in input are integers.

1 \leq N, Q \leq 2 \times 10^5

0 \leq S_i < T_i \leq 10^9

1 \leq X_i \leq 10^9

0 \leq D_1 < D_2 < ... < D_Q \leq 10^9

If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Input

Input is given from Standard Input in the following format:

N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q

Output

Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

Sample Input 1

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

Sample Output 1

2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.

The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.

The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.



Sample input:
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8


Sample output:
2
2
10
-1
13
-1

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q

import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
skip = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    #print(left, right)
    for i in range(left, right):
        #print(i)
        if ans[i] == -1:
            ans[i] = x
    
#print(walkers)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    #print(left, right)
    for i in range(left, right):
        #print(i)
        ans[i] = x
    
#print(walkers)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = dict()
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    #print(left, right)
    for i in range(left, right):
    #   #print(i)
        ans[walkers[i]] = x
    walkers = walkers[:left] + walkers[right:]
    
#print(walkers)
for d in D:
    if d in ans:
        print(ans[d])
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    #print(left, right)
    ans = ans[:left] + [x] * (right-left) + ans[right:]
    #for i in range(left, right):
    #    #print(i)
    #    ans[i] = x
    
#print(walkers)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    #print(left, right)
    for i in range(left, right):
        #print(i)
        ans[i] = x
    
#print(walkers)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = dict()
for x, s, t in roadworks:
    for i in range(s, t+1):
        i = max(0, i-x)
        stops[i] = x
#print(stops)
for d in D:
    if d+1 in stops:
        print(stops[d+1])
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = defaultdict(lambda: -1)
for x, s, t in roadworks:
    for i in range(s, t+1):
        i = max(0, i-x)
        stops[i] = x
#print(stops)
for d in D:
    print(stops[d+1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Aug  9 00:23:59 2019

@author: miz18
"""

import sys
input = sys.stdin.readline

def main(): 
    N,Q = list(map(int,input().split()))
     
    road = []
    r_append = road.append
    x_list = []
    x_append = x_list.append
    for i in range(N):
        s,t,x = list(map(int,input().split()))
        r_append(("s",s-x,x,0))
        r_append(("t",t-x,x,0))
        x_append(x)
     
    for i in range(Q):
        d = int(input())
        r_append(("m",d,i,1))
     
    road.sort(lambda x:x[3])
    road.sort(lambda x:x[1])
     
    x_list = list(set(x_list))
    x_list.sort()
     
    x2i_dict = {}
    for i,x in enumerate(x_list):
        x2i_dict[x]=i
     
     
    class BIT:
                
        def __init__(self, L):
            self.N = len(L)
            self.bit = [0]*self.N
            for i,l in enumerate(L):
                self.add(i,l)
     
        def add(self, a, w):
            x = a + 1
            for i in range(1000):
                self.bit[x-1] += w
                x += x & -x
                if x > self.N:
                    break
     
        def sum(self, a):
            x = a+1
            ret = 0
            for i in range(1000):
                ret += self.bit[x-1]
                x -= x & -x
                if x <= 0:
                    break        
            return ret
     
    def bisectR(l,r,bit):
        while r-l>1:
            if bit.sum((l+r)//2)>0:
                r = (l+r)//2
            else:
                l = (l+r)//2
        return r
     
    
     
    bit = BIT([0]*len(x_list))
    b_add = bit.add
    
    ans = [0]*Q
    for r in road:
        if r[0]=="s":
            b_add(x2i_dict[r[2]],1)
        elif r[0]=="t":
            b_add(x2i_dict[r[2]],-1)
        else:
            if bit.sum(len(x_list)-1)==0:
                ans[r[2]]=-1
            elif bit.sum(0)>0:
                ans[r[2]]=x_list[0]
            else:
                i = bisectR(0,len(x_list)-1,bit)
                ans[r[2]] = x_list[i]
     
    for a in ans:
        print(a)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

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

    road = []
    x_list = []
    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append((s-x,x,0))
        road.append((t-x,x,1))
        x_list.append(x)

    for i in range(Q):
        d = int(input())
        road.append((d,i,2))

    road.sort(lambda x:x[2])
    road.sort(lambda x:x[0])

    x_list = list(set(x_list))
    x_list.sort()

    x2i_dict = {}
    for i,x in enumerate(x_list):
        x2i_dict[x]=i


    class BIT:
            
        def __init__(self, L):
            self.N = len(L)
            self.bit = [0]*self.N
            for i,l in enumerate(L):
                self.add(i,l)

        def add(self, a, w):
            x = a + 1
            for i in range(1000):
                self.bit[x-1] += w
                x += x & -x
                if x > self.N:
                    break

        def sum(self, a):
            x = a+1
            ret = 0
            for i in range(1000):
                ret += self.bit[x-1]
                x -= x & -x
                if x <= 0:
                    break        
            return ret

    xn=len(x_list)

    bit = BIT([0]*xn)

    def bisectR(l,r):
        while r-l>1:
            if bit.sum((l+r)//2)>0:
                r = (l+r)//2
            else:
                l = (l+r)//2
        return r


    ans = [0]*Q
    for r in road:
        if r[2]==0:
             bit.add(x2i_dict[r[1]],1)
        elif r[2]==1:
            bit.add(x2i_dict[r[1]],-1)
        else:
            if bit.sum(xn-1)==0:
               ans[r[1]]=-1
            elif bit.sum(0)>0:
                ans[r[1]]=x_list[0]
            else:
                i = bisectR(0,xn-1)
                ans[r[1]] = x_list[i]
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

road = []
x_list = []
for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append((s-x,x,0))
    road.append((t-x,x,1))
    x_list.append(x)

for i in range(Q):
    d = int(input())
    road.append((d,i,2))

road.sort(lambda x:x[2])
road.sort(lambda x:x[0])

x_list = list(set(x_list))
x_list.sort()

x2i_dict = {}
for i,x in enumerate(x_list):
    x2i_dict[x]=i


class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret


xn=len(x_list)
bit = BIT([0]*xn)

def bisectR(l,r):
    while r-l>1:
        if bit.sum((l+r)//2)>0:
            r = (l+r)//2
        else:
            l = (l+r)//2
    return r


ans = [0]*Q
for r in road:
    if r[2]==0:
        bit.add(x2i_dict[r[1]],1)
    elif r[2]==1:
        bit.add(x2i_dict[r[1]],-1)
    else:
        if bit.sum(xn-1)==0:
            ans[r[1]]=-1
        elif bit.sum(0)>0:
            ans[r[1]]=x_list[0]
        else:
            i = bisectR(0,xn-1)
            ans[r[1]] = x_list[i]
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

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

road = []
x_list = []
for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append(("s",s-x,x,0))
    road.append(("t",t-x,x,0))
    x_list.append(x)

for i in range(Q):
    d = int(input())
    road.append(("m",d,i,1))

road.sort(lambda x:x[3])
road.sort(lambda x:x[1])

x_list = list(set(x_list))
x_list.sort()

x2i_dict = {}
for i,x in enumerate(x_list):
    x2i_dict[x]=i


class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

def bisectR(l,r,bit):
    while r-l>1:
        if bit.sum((l+r)//2)>0:
            r = (l+r)//2
        else:
            l = (l+r)//2
    return r


bit = BIT([0]*len(x_list))
ans = [0]*Q
for r in road:
    if r[0]=="s":
        bit.add(x2i_dict[r[2]],1)
    elif r[0]=="t":
        bit.add(x2i_dict[r[2]],-1)
    else:
        if bit.sum(len(x_list)-1)==0:
            ans[r[2]]=-1
        elif bit.sum(0)>0:
            ans[r[2]]=x_list[0]
        else:
            i = bisectR(0,len(x_list)-1,bit)
            ans[r[2]] = x_list[i]

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import copy 
N,Q=map(int,input().split())
J1=[[0 for i in range(3)] for j in range(N)]
D=[0]*Q
for i in range(N):
  J1[i]=list(map(int,input().split()))
for i in range(Q):
  D[i]=int(input())
J1=sorted(J1, key=lambda x: x[2])
for i in range(Q):
  t=D[i]
  J=copy.copy(J1)
  while J:
    if t-D[i]==J[0][2] and J[0][0]-0.5<=t and t <= J[0][1]-0.5:
      print(t-D[i])
      break
    elif t-D[i]==J[0][2] and (J[0][0]-0.5>=t or t >= J[0][1]-0.5):
      if len(J)>=2:
        del(J[0])
      elif len(J)==1:
        print(-1)
        break
    elif t-D[i] != J[0][2]:
      t=t+1
  if J==[]:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
N, Q = map(int, input().split())
evs = [None] * 2*N
for i in range(N):
    s, t, x = map(int, input().split())
    evs[2*i] = [s-x, 1, x]
    evs[2*i+1] = [t-x, -1, x]
evs.sort()
s = set()
h = []
dic = defaultdict(int)
i, NN = 0, 2*N
for q in range(Q):
    d = int(input())
    while i < NN and evs[i][0] <= d:
        r, f, x = evs[i]
        if f == 1:
            s.add(x)
            heappush(h, x)
            dic[x] += 1
        else:
            s.remove(x)
            dic[x] -= 1
        i += 1
    if len(s):
        while h:
            p = heappop(h)
            if dic[p] > 0:
                heappush(h, p)
                break
        print(p)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
N, Q = map(int, input().split())
evs = [None] * 2*N
for i in range(N):
    s, t, x = map(int, input().split())
    evs[2*i] = [s-x, 1, x]
    evs[2*i+1] = [t-x, -1, x]
evs.sort()
s = set()
INF = 10**20
s.add(INF)
i, NN = 0, 2*N
for q in range(Q):
    d = int(input())
    while i < NN and evs[i][0] <= d:
        r, f, x = evs[i]
        if f == 1:
            s.add(x)
        else:
            s.remove(x)
        i += 1
    ans = min(s)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Submission status: Time Limit Exceeded

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

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q


for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append([lt,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


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



for i in range(Q):
    t = int(input())
    hitos.append(t)
for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l)
     rind  = bisect.bisect_left(hitos,r)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)

Submission status: Time Limit Exceeded

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

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q


for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,rt,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


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



for i in range(Q):
    t = int(input())
    hitos.append(t)
for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l)
     rind  = bisect.bisect_left(hitos,r)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)

Submission status: Time Limit Exceeded

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

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q


for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,rt,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


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



for i in range(Q):
    t = int(input())
    hitos.append(t)
for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l)
     rind  = bisect.bisect_left(hitos,r)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp
ans = list(map(str,ans))
print("\n".join( ans))

Submission status: Time Limit Exceeded

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

hitos = []
ans = [-1] * Q
queries =[]
heapq.heapify(queries)
events = {}
for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,-1,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所
    queries.append((rt,1,X)) # 1 → 削除クエリ



for i in range(Q):
    t = int(input())
    queries.append((t,0,-99)) # 0 → チェッククエリ
queries.sort(key = lambda x:x[0])
for t,kind,x in queries:
    if kind == 0:
        if len(events) > 0:
            print(min(events))
        else:
            print(-1)
    if kind == -1:
        events[x] = x
    if kind == 1:
        events.pop(x)

Submission status: Time Limit Exceeded

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

hitos = []
ans = [-1] * Q
queries =[]
heapq.heapify(queries)
events = []
for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,-1,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所
    queries.append((rt,1,X)) # 1 → 削除クエリ



for i in range(Q):
    t = int(input())
    queries.append((t,0,-99)) # 0 → チェッククエリ
queries.sort(key = lambda x:x[0])
for t,kind,x in queries:
    if kind == 0:
        if len(events) > 0:
            print(min(events))
        else:
            print(-1)
    if kind == -1:
        events.append(x)
    if kind == 1:
        events.remove(x)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,Q = list(map(int,input().split(" ")))

hitos = []
ans = [-1] * Q
queries = []
events = []
for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,-1,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所
    queries.append((rt,1,X)) # 1 → 削除クエリ


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

for i in range(Q):
    t = int(input())
    queries.append((t,0,-99)) # 0 → チェッククエリ
queries.sort(key = lambda x:x[0])
for t,kind,x in queries:
    if kind == 0:
        if len(events) > 0:
            print(min(events))
        else:
            print(-1)
    if kind == -1:
        events.append(x)
    if kind == 1:
        events.remove(x)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
works = [[0] * 2 for i in range(N)]

for i in range(N):
    works[i] = list(map(int, input().split()))
works = sorted(works, key=lambda x: x[2])  # 2番目の要素(工事現場の座標)でソート

for i in range(N):
    works[i][0] = works[i][0]-works[i][2]
    works[i][1] = works[i][1]-works[i][2]

people = [0 for i in range(Q)]
for i in range(Q):
    people[i] = int(input())

# print(works)
# print(people)

for start_time in people:
    for i, st in enumerate(works):
        if st[0] <= start_time and start_time < st[1]:
            # print(st)
            print(st[2])
            break
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from bisect import bisect, bisect_left
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

event = []
for s, t, x in X:
    if t - x - 1 < 0:
        continue
    heappush(event, (bisect_left(D, s - x), bisect(D, t - x - 1), x))

passesd_event = []
ans = [0] * Q
for i in range(Q):
    while len(event) > 0 and event[0][0] <= i:
        a, b, x = heappop(event)
        heappush(passesd_event, (x, a, b))
        
    while len(passesd_event) > 0 and passesd_event[0][2] <= i:
        heappop(passesd_event)
        
    ans[i] = -1 if len(passesd_event) == 0 else passesd_event[0][0]
    
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from bisect import bisect, bisect_left
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

event = []
for s, t, x in X:
    heappush(event, (bisect_left(D, s - x), bisect(D, t - x - 1), x))

passesd_event = []
ans = [0] * Q
for i in range(Q):
    while len(event) > 0 and event[0][0] <= i:
        a, b, x = heappop(event)
        heappush(passesd_event, (x, a, b))
        
    while len(passesd_event) > 0 and passesd_event[0][2] <= i:
        heappop(passesd_event)
        
    ans[i] = -1 if len(passesd_event) == 0 else passesd_event[0][0]
    
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

event = []
for s, t, x in X:
    event.append((s - x, -1, x))
    event.append((t - x, 0, x))
    
for i, d in enumerate(D):
    event.append((d, 1, i))
    
event.sort()
buffer = []
ans = [0] * Q
for _, q, x in event:
    if q == -1:
        idx = bisect(buffer, x)
        if idx < len(buffer):
            buffer = buffer[:idx] + [x] + buffer[idx:]
        else:
            buffer.append(x)
    elif q == 0:
        buffer.pop(bisect(buffer, x) - 1)
    else:
        ans[x] = -1 if len(buffer) == 0 else buffer[0]
        
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heapify
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

event = []
for s, t, x in X:
    event.append((s - x, -1, x))
    event.append((t - x, 0, x))
    
for i, d in enumerate(D):
    event.append((d, 1, i))
    
event.sort()
buffer = []
ans = [0] * Q
for _, q, x in event:
    if q == -1:
        heappush(buffer, x)
    elif q == 0:
        buffer.remove(x)
        heapify(buffer)
    else:
        ans[x] = -1 if len(buffer) == 0 else buffer[0]
        
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

event = []
for s, t, x in X:
    event.append((s - x, -1, x))
    event.append((t - x, 0, x))
    
for i, d in enumerate(D):
    event.append((d, 1, i))
    
event.sort()
buffer = []
ans = []
for _, q, x in event:
    if q == -1:
        heappush(buffer, x)
    elif q == 0:
        buffer.remove(x)
    else:
        ans.append(-1 if len(buffer) == 0 else min(buffer))
        
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

event = []
for s, t, x in X:
    event.append((s - x, -1, x))
    event.append((t - x, 0, x))
    
for i, d in enumerate(D):
    event.append((d, 1, i))
    
event.sort()
buffer = []
ans = []
for _, q, x in event:
    if q == -1:
        buffer.append(x)
    elif q == 0:
        buffer.remove(x)
    else:
        ans.append(-1 if len(buffer) == 0 else min(buffer))
        
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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()
    e = []
    for i in range(n):
        s,t,x = LI()
        e.append((s-x,x,1))
        e.append((t-x,x,0))
    e.sort()
    m = 2*n
    q = set()
    j = 0
    ans = float("inf")
    for i in range(Q):
        d = I()
        while j < m:
            t,x,k = e[j]
            if d < t:
                break
            if k:
                q.add(x)
                if x < ans:
                    ans = x
            else:
                q.remove(x)
                if ans == x:
                    if q:
                        ans = min(q)
                    else:
                        ans = float("inf")
            j += 1
        print(-1 if ans == float("inf") else ans)
    return

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

    return

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