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:
# Treap
#平衡二分木　乱数を用いてできるだけ平衡を保つらしい　
#priorityには乱数を入れること
# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c

# insert a node with key = val and priority = pri
root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    # [<left>, <right>, <key>, <priority>, <count>]
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def treapmin():
    global root
    x=root
    if not x:
        return -1
    while x[0]:
        x=x[0]
    return x[2]

import sys,random

input=sys.stdin.readline

def solve():
    N,Q=map(int,input().split())
    event=[]
    event_append=event.append
    for i in range(0,N):
        s,t,x=map(int,input().split())
        event_append((s-x,1,x))
        event_append((t-x,-1,x))
    
    for i in range(0,Q):
        d=int(input())
        event_append((d,2,d))
    
    event.sort()
    for j in range(len(event)):
        t,e,x=event[j]
        if e==1:
            insert(x,random.randint(1,100000))
        elif e==-1:
            delete(x)
        else:
            print(treapmin())

if __name__=='__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# Treap
#平衡二分木　乱数を用いてできるだけ平衡を保つらしい　
#priorityには乱数を入れること
# d = 0: right rotation
# d = 1: left rotation
def rotate(nd, d):
    c = nd[d]
    if d:
        e = c[1]
        nd[1] = c[0]
        c[0] = nd
    else:
        e = c[0]
        nd[0] = c[1]
        c[1] = nd

    r = c[4] = nd[4]
    nd[4] = r - (e[4] if e else 0) - 1
    return c

# insert a node with key = val and priority = pri
root = None
def insert(val, pri):
    global root
    st = []
    dr = []
    x = root
    while x:
        st.append(x)
        if x[2] == val:
            return
        d = (x[2] < val)
        dr.append(d)
        x = x[d]

    # [<left>, <right>, <key>, <priority>, <count>]
    nd = [None, None, val, pri, 1]
    while st:
        x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] += 1
        if x[3] >= nd[3]:
            break
        rotate(x, d)
    else:
        root = nd

    for x in st:
        x[4] += 1

def __delete(nd):
    st = []; dr = []
    while nd[0] or nd[1]:
        l = nd[0]; r = nd[1]
        d = (l[3] <= r[3]) if l and r else (l is None)
        st.append(rotate(nd, d))
        dr.append(d ^ 1)
    nd = x = None
    while st:
        nd = x; x = st.pop(); d = dr.pop()
        x[d] = nd
        x[4] -= 1
    return x

def delete(val):
    global root
    x = root

    st = []
    y = None
    while x:
        if val == x[2]:
            break
        y = x; d = (x[2] < val)
        st.append(y)
        x = x[d]
    else:
        return

    if y:
        y[d] = __delete(x)
        for x in st:
            x[4] -= 1
    else:
        root = __delete(x)

def treapmin():
    global root
    x=root
    if not x:
        return -1
    while x[0]:
        x=x[0]
    return x[2]

import sys,random

input=sys.stdin.readline

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

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

event.sort()
for j in range(len(event)):
    t,e,x=event[j]
    time=t
    if e==1:
        insert(x,random.randint(1,100000))
    elif e==-1:
        delete(x)
    else:
        print(treapmin())

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
kouji=[]
for i in range(0,N):
    s,t,x=map(int,input().split())
    kouji.append([x,s,t])

d=[]
for i in range(0,Q):
    d.append(int(input()))

kouji.sort(reverse=True)

# N: 処理する区間の長さ

N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1,-1)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

time=0
for i in range(0,N):
    x,s,t=kouji[i]
    start=0
    end=Q-1
    while end-start>1:
        test=(end+start)//2
        if d[test]>=s-x:
            end=test
        else:
            start=test
    if d[start]>=s-x:
        l=start
    elif d[end]>=s-x:
        l=end
    else:
        l=Q

    start=0
    end=Q-1
    while end-start>1:
        test=(end+start)//2
        if t-x-1>=d[test]:
            start=test
        else:
            end=test
    if t-x-1>=d[end]:
        r=end
    elif t-x-1>=d[start]:
        r=start
    else:
        r=-1
    if r!=-1 and l!=Q and r>=l:
        update(l,r+1,(time,x))
    time+=1

for i in range(0,Q):
    print(query(i))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    events = []
    for i in range(N):
        S, T, X = map(int, input().split())
        events.append((S-X-0.5, 1, X))
        events.append((T-X-0.5, 0, X))
    for i in range(Q):
        D = int(input())
        events.append((D, 2, i))

    events.sort()

    anss = [-1] * Q
    PQ = []
    isClosed = dict()
    for tm, tp, x in events:
        if tp == 0:
            isClosed[x] = 0
        elif tp == 1:
            isClosed[x] = 1
            heappush(PQ, x)
        else:
            while PQ:
                if isClosed[PQ[0]] == 1:
                    anss[x] = PQ[0]
                    break
                heappop(PQ)

    print('\n'.join(map(str, anss)))


solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    events = []
    for i in range(N):
        S, T, X = map(int, input().split())
        events.append((S-X-0.5, 1, X))
        events.append((T-X-0.5, 0, X))
    for i in range(Q):
        D = int(input())
        events.append((D, 2, i))

    events.sort()

    anss = [-1] * Q
    PQ = []
    isClosed = defaultdict(int)
    for tm, tp, x in events:
        if tp == 0:
            isClosed[x] = 0
        elif tp == 1:
            isClosed[x] = 1
            heappush(PQ, x)
        else:
            while PQ:
                if isClosed[PQ[0]] == 1:
                    anss[x] = PQ[0]
                    break
                heappop(PQ)

    print('\n'.join(map(str, anss)))


solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = []
for _ in range(N):
    S, T, X = map(int, input().split())
    events.append((S-X, X))
    events.append((T-X, -X))
events.sort()
events = deque(events)
ans = [0] * Q
cur = []
remove = defaultdict(int)
for i in range(Q):
    D = int(input())
    while events and events[0][0] <= D:
        t, x = events.popleft()
        if x > 0:
            heappush(cur, x)
        else:
            remove[-x] += 1
    while cur and remove[cur[0]]:
        remove[cur[0]] -= 1
        heappop(cur)
    ans[i] = cur[0] if cur else -1
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
hq=[]
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
    heapq.heappush(hq,x)
  elif f==-1:
    stop_set.remove(x)
  else:
    if len(stop_set)>0:
      while(True):
        if hq[0] in stop_set:
          answer_dic[t]=hq[0]
          break
        else:
          heapq.heappop(hq)
    else:
      answer_dic[t]=-1
#print(answer_dic)

for d in dlist:
  print(answer_dic[d])

Submission status: Time Limit Exceeded

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

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
  elif f==-1:
    stop_set.remove(x)
  else:
    if len(stop_set)>0:
      answer_dic[t]=min(stop_set)
#print(answer_dic)

for d in dlist:
  if d in answer_dic:
    print(answer_dic[d])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n, q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort(key=lambda x: x[2])
d = [-float('inf')] + [int(input()) for _ in range(q)]
p = list(range(1, q + 2))
ans = [-1] * (q + 1)
for s, t, x in l:
    idx1 = bisect_left(d, s - x)
    idx2 = bisect_left(d, t - x)
    j = idx1
    while j < q + 1 and j < idx2:
        if ans[j] == -1:
            ans[j] = x
        p[j - 1] = idx2
        j = p[j]
for x in ans[1:]:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq as hq
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, Q = map(int, rl().split())
    event = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        event.append((t - x, 0, x))
        event.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        event.append((d, 2, -1))
    event.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in event:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            hq.heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    hq.heappop(pos_hq)
                else:
                    break
            ans.append(pos_hq[0] if pos_hq else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

n, q = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(n)]
task = []
for s, t, x in STX:
    task.append((t - x, 0, x))
    task.append((s - x, 1, x))
for i in range(q):
    d = int(input())
    task.append((d, 2, i))

task.sort()
kouho = set()
kouho_hp = []
ans = [-1] * q
for a, b, c in task:
    if b == 0:
        kouho.remove(c)
    if b == 1:
        kouho.add(c)
        heappush(kouho_hp, c)
    if b == 2:
        while kouho_hp and kouho_hp[0] not in kouho:
            heappop(kouho_hp)
        if not kouho_hp:
            continue
        else:
            ans[c] = kouho_hp[0]
        # heapは0-indexが最小値になっているからheapified_list[0]でもよい
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    if t-x > 0:
        imos.append((max(s-x,0),x))
        imos.append((t-x,-x))
ans = set()
j = 0
l = len(imos)
imos.sort()
for i in range(q):
    d = int(input())
    while j < l:
        now,stop = imos[j]
        if now > d:
            break
        if stop > 0:
            ans.add(stop)
        else:
            ans.remove(-stop)
        j += 1
    if ans:
        print(min(ans))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:m = stop
    else:
        ans.remove(-stop)
        if m == -stop:flag = False

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
for t,stop in imos:
    if stop == 1e100:
        if ans:
            print(min(ans))
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
    else:
        ans.remove(-stop)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
l = len(imos)
imos.sort()
for i in range(q):
    d = int(input())
    while j < l:
        now,stop = imos[j]
        if now > d:
            break
        if stop > 0:
            ans.add(stop)
        else:
            ans.remove(-stop)
        j += 1
    if ans:
        print(min(ans))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    if t-x > 0:
        imos.append((max(s-x,0),x))
        imos.append((t-x,-x))
ans = set()
j = 0
l = len(imos)
imos.sort()
for i in range(q):
    d = int(input())
    while j < l:
        now,stop = imos[j]
        if now > d:
            break
        if stop > 0:
            ans.add(stop)
        else:
            ans.remove(-stop)
        j += 1
    if ans:
        print(min(ans))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,q = map(int,input().split())
imos = []
heapq.heapify(imos)
for i in range(n):
    s,t,x = map(int,input().split())
    if t-x > 0:
        heapq.heappush(imos,(max(s-x,0),x))
        heapq.heappush(imos,(t-x,-x))
ans = set()
now = 0
for i in range(q):
    d = int(input())
    while imos:
        now,stop = heapq.heappop(imos)
        if now > d:
            heapq.heappush(imos,(now,stop))
            break
        if stop > 0:
            ans.add(stop)
        else:
            ans.remove(-stop)
    if ans:
        print(min(ans))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N,Q = map(int,input().split())
    ivents =[]
    for i in range(N):
        S,T,X = map(int,input().split())
        ivents.append([S-X,X,True])
        ivents.append([T-X,X,False])

    ivents.sort()
    using = set()
    index = 0
    for i in range(Q):
        D = int(input())
        while index<len(ivents) and ivents[index][0] <= D:
            Time,Posi,flg = ivents[index]
            if flg:
                using.add(Posi)
            else:
                using.discard(Posi)
            index += 1
        
        if using:
            print(min(using))
        else:
            print(-1)

            
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N,Q = map(int,input().split())
    ivents =[]
    for i in range(N):
        S,T,X = map(int,input().split())
        ivents.append([S-X,X,True])
        ivents.append([T-X,X,False])

    ivents.sort(key = lambda x:x[0])
    using = set()
    index = 0
    for i in range(Q):
        D = int(input())
        while index<len(ivents) and ivents[index][0] <= D:
            Time,Posi,flg = ivents[index]
            if flg:
                using.add(Posi)
            else:
                using.discard(Posi)
            index += 1
        
        if using:
            print(min(using))
        else:
            print(-1)

            
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def resolve():
    N,Q = map(int,input().split())
    iventso =[]
    for i in range(N):
        S,T,X = map(int,input().split())
        iventso.append([S-X,X,True])
        iventso.append([T-X,X,False])

    iventso.sort(key = lambda x:x[0])
    using = set()

    ivents = deque(iventso)



    for i in range(Q):
        D = int(input())
        while ivents and ivents[0][0] <= D:
            Time,Posi,flg = ivents[0]
            if flg:
                using.add(Posi)
            else:
                using.discard(Posi)
            ivents.popleft()
        
        if using:
            print(min(using))
        else:
            print(-1)

            
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N,Q = map(int,input().split())
    ivents =[]
    for i in range(N):
        S,T,X = map(int,input().split())
        ivents.append([S-X,X,True])
        ivents.append([T-X,X,False])

    ivents.sort(key = lambda x:x[0])
    using = set()

    for i in range(Q):
        D = int(input())
        while ivents and ivents[0][0] <= D:
            Time,Posi,flg = ivents[0]
            if flg:
                using.add(Posi)
            else:
                using.discard(Posi)
            ivents = ivents[1:]
        
        if using:
            print(min(using))
        else:
            print(-1)

            
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N,Q = map(int,input().split())
    ivents =[]
    for i in range(N):
        S,T,X = map(int,input().split())
        ivents.append([S-X,X,True])
        ivents.append([T-X,X,False])

    ivents.sort(key = lambda x:x[0])
    using = set()

    for i in range(Q):
        D = int(input())
        while ivents and ivents[0][0] <= D:
            Time,Posi,flg = ivents[0]
            if flg:
                using.add(Posi)
            else:
                using.discard(Posi)
            ivents = ivents[1:]
        
        if using:
            print(min(using))
        else:
            print(-1)

            
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8"""
        output = """2
2
10
-1
13
-1"""
        self.assertIO(input, output)

def ins(using:set,posision:int):
    using.add(posision)

def rem(using:set,posision:int):
    using.discard(posision)


def resolve():
    N,Q = map(int,input().split())
    ivents =[]
    for i in range(N):
        S,T,X = map(int,input().split())
        ivents.append([S-X,X,ins])
        ivents.append([T-X,X,rem])

    ivents.sort(key = lambda x:x[0])
    using = set()

    for i in range(Q):
        D = int(input())
        while ivents and ivents[0][0] <= D:
            ivents[0][2](using,ivents[0][1])
            ivents = ivents[1:]
        
        if using:
            print(min(using))
        else:
            print(-1)


    
    


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8"""
        output = """2
2
10
-1
13
-1"""
        self.assertIO(input, output)

def ins(using:set,posision:int):
    using.add(posision)

def rem(using:set,posision:int):
    using.discard(posision)


def resolve():
    N,Q = map(int,input().split())
    ivents =[]
    for i in range(N):
        S,T,X = map(int,input().split())
        ivents.append([S-X,X,ins])
        ivents.append([T-X,X,rem])

    ivents.sort(key = lambda x:x[0])
    using = set()

    for i in range(Q):
        D = int(input())
        while ivents and ivents[0][0] <= D:
            ivents[0][2](using,ivents[0][1])
            ivents = ivents[1:]
        
        if using:
            print(min(using))
        else:
            print(-1)


    
    


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
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.sort(key=lambda _: _[2])
S, T, X = [], [], []
for stx in STX:
    s, t, x = stx
    S.append(s)
    T.append(t)
    X.append(x)
D = [int(input()) for j in range(q)]

A = np.zeros(q, dtype=int) - 1
for i in range(n-1, -1, -1):
    l = bisect.bisect_left(D, S[i]-X[i])
    r = bisect.bisect_left(D, T[i]-X[i])
    A[l:r] = X[i]
for a in A:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  # 1-indexed
        self.N = N

    def add(self, i, x):
        """tree[i]と関連個所にxを加える"""
        tree = self.tree
        N = self.N
        while i <= N:
            tree[i] += x
            i += i & (-i)

    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def binary_search(self, x):
        """区間和 >=x となる最小のindex"""
        tree = self.tree
        N = self.N
        i = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and tree[i + step] < x:
                i += step
                x -= tree[i]
            step >>= 1
        return i + 1


def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time position')

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

    go = []
    stop = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, input().split())
        stop.append(Event(time=s - x, position=x))
        go.append(Event(time=t - x, position=x))
        xs.add(x)

    xs = sorted(xs)

    stop.sort(key=attrgetter('time'))
    go.sort(key=attrgetter('time'))

    stop = deque(stop)
    go = deque(go)

    compress = {x: i for i, x in enumerate(xs, 1)}
    decompress = {i: x for i, x in enumerate(xs, 1)}

    ans = []
    b = BIT(N)
    for _ in range(Q):
        d = int(input())
        while go and go[0].time <= d:
            e = go.popleft()
            p = compress[e.position]
            b.add(p, -1)
        while stop and stop[0].time <= d:
            e = stop.popleft()
            p = compress[e.position]
            b.add(p, 1)

        compressed_ind = b.binary_search(1)
        ind = decompress.get(compressed_ind, -1)
        ans.append(ind)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  # 1-indexed
        self.N = N

    def add(self, i, x):
        """tree[i]と関連個所にxを加える"""
        tree = self.tree
        N = self.N
        while i <= N:
            tree[i] += x
            i += i & (-i)

    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def binary_search(self, x):
        """区間和 >=x となる最小のindex"""
        tree = self.tree
        N = self.N
        i = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and tree[i + step] < x:
                i += step
                x -= tree[i]
            step >>= 1
        return i + 1


def main():
    from collections import deque, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time typ position')

    GO = 0
    STOP = 1

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

    works = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, input().split())
        e1 = Event(time=s - x, typ=STOP, position=x)
        e2 = Event(time=t - x, typ=GO, position=x)
        works.append(e1)
        works.append(e2)
        xs.add(x)

    xs = sorted(xs)

    works.sort(key=attrgetter('time', 'typ'))
    works = deque(works)

    compress = {x: i for i, x in enumerate(xs, 1)}
    decompress = {i: x for i, x in enumerate(xs, 1)}

    ans = []
    b = BIT(N)
    for _ in range(Q):
        d = int(input())
        while works and works[0].time <= d:
            e = works.popleft()
            p = compress[e.position]
            if e.typ == GO:
                b.add(p, -1)
            else:
                # STOP
                b.add(p, 1)

        compressed_ind = b.binary_search(1)
        ind = decompress.get(compressed_ind, -1)
        ans.append(ind)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
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.sort(key=lambda _: _[2])
S, T, X = [], [], []
for stx in STX:
    s, t, x = stx
    S.append(s)
    T.append(t)
    X.append(x)
D = [int(input()) for j in range(q)]
A = [-1 for j in range(q)]
st = set()
for i in range(n):
    l = bisect.bisect_left(D, S[i]-X[i])
    r = bisect.bisect_left(D, T[i]-X[i])
    lr = set(range(l, r))
    for j in lr.difference(st):
        A[j] = X[i]
    st = st.union(lr)
for a in A:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush, heappop
N, Q = map(int, input().split())
E = []

for i in range(N):
    s, t, x = map(int, input().split())
    E.append((0, t - x, x, i))
    E.append((1, s - x, x, i))

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

E.sort(key=lambda a: a[1], reverse=True)

ans = []
que = [(10**18, -1)]
V = set()
for d in D:
    while E and E[-1][1] <= d:
        f, _, x, i = E.pop()
        if f == 0:
            V.add(i)
        else:
            heappush(que, (x, i))
    while que[0][1] in V:
        heappop(que)
    ans.append(que[0][0])

ans = [a if a < 10**18 else -1 for a in ans]
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def main():    
    import bisect
    n,q = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l = sorted(l,key = lambda x: x[2])
    d = [int(input()) for i in range(q)]

    ans = [-1]*q
    skip = [-1]*q
    for s,t,x in l:
        le = bisect.bisect_left(d,s-x)
        ri = bisect.bisect_left(d,t-x)
        while le < ri:
            if skip[le] == -1:
                ans[le] = x
                skip[le] = ri
                le += 1
            else:
                le = skip[le]

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,q = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l = sorted(l,key = lambda x: x[2])
d = [int(input()) for i in range(q)]

ans = [-1]*q
skip = [-1]*q
for s,t,x in l:
    le = bisect.bisect_left(d,s-x)
    ri = bisect.bisect_left(d,t-x)
    while le < ri:
        if skip[le] == -1:
            ans[le] = x
            skip[le] = ri
            le += 1
        else:
            le = skip[le]

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
N, Q = map(int, input().split())
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((2*s-2*x-1, 0, x))
    X.append((2*t-2*x-1, 1, x))

inf = 10**18
X.append((-inf, 0, inf))
X.append((inf, 1, inf))

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

from heapq import *
from collections import defaultdict
#print(X[1:-1])
j = 0
ll = []
vs = set()
d = defaultdict(int)
for _ in range(Q):
    q = int(input())
    while 1:
        u, f, x = X[j]
        if u > 2*q:
            break
        if f:
            d[x] += 1
        else:
            heappush(ll, x)
        j += 1
    while 1:
        x = heappop(ll)
        if d[x] > 0:
            d[x] -= 1
            continue
        heappush(ll, x)
        if x == inf:
            print(-1)
        else:
            print(x)
        break