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 .

Solution (Python):
import sys
import heapq
from collections import defaultdict
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
task = []
for _ in range(N):
    s, t, x = map(int, input().split())
    start = t - x
    end = s - x
    task.append((start, -1, x))
    task.append((end, 1, x))
task.sort(reverse=True)

cand = []
discard = defaultdict(int)
ans = []

for _ in range(Q):
    d = int(input())
    while task and task[-1][0] <= d:
        _, flag, x = task.pop()
        if flag == 1:
            heapq.heappush(cand, x)
        else:
            discard[x] += 1

    while cand:
        x = cand[0]
        if discard[x] > 0:
            heapq.heappop(cand)
            discard[x] -= 1
        else:
            break

    if cand:
        ans.append(cand[0])
    else:
        ans.append(-1)

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

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが小さい順に工事区間を見て，引っかかるならば区間更新．
    一度値を決定した場所は飛ばしながら更新するようにすればO(Q)
    nxtを入れながら進めば各ノードを2回しか見ないからO(Q)
    事前のソートで NlogN
    """

    
    N,Q=MI()
    xst2=[]
    xi=[[0,0]for _ in range(N)]
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
        xi[i]=[x,i]
    xi.sort()
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
    inf=10**10
    ans=[inf]*(Q+4)
    nxt=[0]*(Q+4)
    for i in range(Q+4):
        nxt[i]=i+1
        
    """
    print(xi)
    print(xst2)"""
    
    
    for i in range(N):
        ii=xi[i][1]
        xx=xst2[ii][0]
        
        
        ss=bisect.bisect_left(D,xst2[ii][1])
        tt=bisect.bisect_left(D,xst2[ii][2])
        j=ss
        while j<tt:
            if ans[j]==inf:
                ans[j]=xx
            jj=j
            j=nxt[j]
            nxt[jj]=tt
        """print(ii,xst2[ii][1],xst2[ii][2],xx,ss,tt)
        print(ans)
        print(nxt)"""

    
        
    for i in range(Q):
        res=ans[i]
        if res==inf:
            print(-1)
        else:
            print(res)
            
        
    
        

main()

Solution (Python):
from heapq import heappush, heappop
N,Q,*L = map(int, open(0).read().split())
X = L[:3*N]
D = L[3*N:]
ls = []
for s,t,x in zip(*[iter(X)]*3):
  ls.append((s-x,1,x))
  ls.append((t-x,0,x))
for i,d in enumerate(D):
  ls.append((d,2,i))
ls.sort()
ans = [0]*Q
S = set()
hq = []
for a,b,c in ls:
  if b==0:
    S.remove(c)
  elif b==1:
    S.add(c)
    heappush(hq,c)
  else:
    while hq and hq[0] not in S:
      heappop(hq)
    ans[c] = hq[0] if hq else -1
print('\n'.join(map(str,ans)))

Solution (Python):
from heapq import heappush, heappop
N,Q,*L = map(int, open(0).read().split())
D = L[3*N:]
ls = []
for i in range(N):
  s,t,x = L[3*i],L[3*i+1],L[3*i+2]
  ls.append((s-x,1,x))
  ls.append((t-x,0,x))
for i,d in enumerate(D):
  ls.append((d,2,i))
ls.sort()
ans = [0]*Q
S = set()
hq = []
for a,b,c in ls:
  if b==0:
    S.remove(c)
  elif b==1:
    S.add(c)
    heappush(hq,c)
  else:
    while hq and hq[0] not in S:
      heappop(hq)
    ans[c] = hq[0] if hq else -1
print('\n'.join(map(str,ans)))

Solution (Python):


"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    
    events.append((s-x,1,x))
    
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)

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


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


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

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


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


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

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left
N, Q = map(int, input().split())
W = [tuple(map(int, input().split())) for _ in range(N)]
W.sort(key=lambda x:x[2])
D = [int(input()) for _ in range(Q)]
ans = [-1]*Q
skip = [-1]*Q
for s, t, x in W:
    l = bisect_left(D, s-x)
    r = bisect_left(D, t-x)
    while l < r:
        if skip[l] == -1:
            ans[l] = x
            skip[l] = r
            l += 1
        else:
            l = skip[l]
print(*ans, sep='\n')

Solution (Python):
import sys
input = lambda: sys.stdin.buffer.readline()
from bisect import bisect_left, bisect_right
INF = float("inf")

class LazySegmentTree:
    INF = float("inf")

    def __init__(self, n):
        self.n = 1 << (n-1).bit_length()
        self.data = [self.INF] * (self.n*2)
        self.lazy = [None] * (self.n*2)
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = min(self.data[i*2], self.data[i*2+1])
        
    def query(self, l, r):
        if not l < r: return self.INF
        self.__propagate(self.__getidx(l, r))

        l += self.n; r += self.n 
        res = self.INF
        while l < r:
            if l & 1:
                res = min(res, self.data[l])
                l += 1
            if r & 1:
                res = min(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def update(self, l, r, x):
        if not l < r: return
        idx = self.__getidx(l, r)
        self.__propagate(idx)

        l += self.n; r += self.n 
        while l < r:
            if l & 1:
                self.data[l], self.lazy[l] = x, x
                l += 1
            if r & 1:
                self.data[r-1], self.lazy[r-1] = x, x
            l >>= 1; r >>= 1
    
        for i in idx:
            self.data[i] = min(self.data[i*2], self.data[i*2+1])

    def __getidx(self, l, r):
        l += self.n; r += self.n 
        lm = l // ((l & -l) << 1)
        rm = r // ((r & -r) << 1)
        res = []
        while l < r:
            if l <= lm: res.append(l)
            if r <= rm: res.append(r)
            l >>= 1; r >>= 1
        while l:
            res.append(l)
            l >>= 1
        return res
    
    def __propagate(self, idx):
        for i in reversed(idx):
            val = self.lazy[i]
            if val is None: continue
            self.lazy[i*2] = val; self.lazy[i*2+1] = val
            self.data[i*2] = val; self.data[i*2+1] = val
            self.lazy[i] = None

def main():
    n, q = map(int, input().split())
    query = [None] * n
    for i in range(n):
        s, t, x = map(int, input().split())
        query[i] = s-x, t-x, x
    d = [int(input()) for _ in range(q)]
    lst = LazySegmentTree(q)

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

    for l, r, x in query:
        lst.update(bisect_left(d, l), bisect_left(d, r), x)

    for i in range(q):
        ans = lst.query(i, i+1)
        print(-1 if ans == INF else ans)

if __name__ == "__main__":
    main()

Solution (Python):


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

    input = sys.stdin.readline
    Event = namedtuple('Event', 'pos start end')
    UC = namedtuple('UC', 'pos end')  

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

    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        e = Event(pos=x, start=s - x, end=t - x)  
        events.append(e)
    events.sort(key=attrgetter('start'))
    events = deque(events)

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

    ans = []
    h = []
    for d in D:
        while events and events[0].start <= d:
            e = events.popleft()
            heappush(h, UC(pos=e.pos, end=e.end))

        while h and h[0].end <= d:
            heappop(h)

        ans.append(h[0].pos if h else -1)

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


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    unique_X=sorted(list(set(X)))
    d={unique_X[i]:i for i,x in enumerate(unique_X)}
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,d[X[i]]))
        l.append((T[i]-X[i],-1,d[X[i]]))
    for i in range(Q):
        l.append((int(input()),2,0))
    l.sort(key=lambda t: t[0])
    b=BIT(len(unique_X))
    for t,q,x in l:
        if q==-1:
            b.add(x,-1)
        elif q==1:
            b.add(x,1)
        else:
            res,_=b.lower_bound(1)
            print(unique_X[res] if res<len(unique_X) else -1)
        


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    """
    計算量の落とし方が全くわからんので以下のコードを参考に写経。。。
    https://atcoder.jp/contests/abc128/submissions/7712981
    """
    N, Q = map(int, input().split())
    work = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        work.append((x, s - x, t - x))
    work.sort(key=lambda x: (x[0], x[1]))
    start = [int(input()) for _ in range(Q)]

    """
    工事箇所を原点にスライドさせる事で考察を易化しておく。
    各工事(x, s, t)に対して（既にs, tは原点への移動を考慮済み）s<=d<tなるdの個数を求めたい
    startは既に昇順に並んでいるので二分探索でs<=d_i<d_{i+1}<...<d_{j-1}<tなるi=left, j=rightを求める。

    そのあと[left, right)をxで埋めていくが、愚直に(right-left)回xを代入していくとO(Q)かかってTLEするので
    skip[left]=(以前に[left, right)を埋めたときのright)を格納しておく。
    これによりansの表を毎度全走査しなくてもよくなり書き込み範囲のオーバーラップがだいぶ削減される。

    しかしskipを使っても飛んだ先がまたskip命令入ってる可能性もあるから、AC出来るのはやや偶然感あり。。。
    """

    ans = [-1] * Q
    skip = [-1] * Q
    for x, s, t in work:
        left = bisect_left(start, s)
        right = bisect_left(start, t)
        while left < right:
            if skip[left] == -1:
                ans[left] = x
                skip[left] = right
                left += 1
            else:
                left = skip[left]

    for i in range(Q):
        print(ans[i])




if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_left as b;n,q=map(int,input().split());w=sorted([list(map(int,input().split()))[::-1]for _ in[0]*n]);p=[int(input())for _ in[0]*q];a=[-1]*q;o=[-1]*q
for x,t,s in w:
  l,r=b(p,s-x),b(p,t-x)
  while l<r:
    if o[l]+1:l=o[l]
    else:a[l],o[l]=x,r;l+=1
print(*a)

Solution (Python):
from bisect import bisect_left,bisect_right
n,q=map(int,input().split())
w=[list(map(int,input().split()))[::-1]for _ in range(n)]
p=[int(input())for _ in range(q)]
w.sort()
ans=[-1]*q
to=[-1]*q
for x,t,s in w:
  l,r=bisect_left(p,s-x),bisect_left(p,t-x)
  while l<r:
    if to[l]==-1:
      ans[l]=x
      to[l]=r
      l+=1
    else:
      l=to[l]
print(*ans)

Solution (Python):
import heapq as hq
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def main():
    n,q = nm()
    tl = []
    ins = list()
    dlt = list()
    vv = [tuple(nm()) for _ in range(n)]
    tl = [(s-x, 1, x) for s, _, x in vv]
    tl.extend([(t-x, 0, x) for _, t, x in vv])
    ww = [ni() for _ in range(q)]
    tl.extend([(t, 2) for t in ww])
    tl.sort()

    for x in tl:
        if x[1] == 1:
            hq.heappush(ins, x[2])
        elif x[1] == 0:
            hq.heappush(dlt, x[2])
            while dlt and ins[0] == dlt[0]:
                hq.heappop(ins)
                hq.heappop(dlt)
        else:
            print(-1 if not ins else ins[0])
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys

input=sys.stdin.readline

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)



N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1,-1)


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

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

Solution (Python):
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()

Solution (Python):
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()

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

N, Q = map(int, input().split())
events = [None] * (2*N)
for i in range(N):
    S, T, X = map(int, input().split())
    events[2*i] = (S-X, X)
    events[2*i+1] = (T-X, -X)
events.sort(key=lambda x: x[0])
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')

Solution (Python):
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()

Solution (Python):
from heapq import heappush, heappop
import sys

input = sys.stdin.buffer.readline


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]
        
print(*ans, sep="\n")

Solution (Python):
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())
    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
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False

Solution (Python):


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

    input = sys.stdin.readline
    Event = namedtuple('Event', 'pos start end')
    UC = namedtuple('UC', 'pos end')  

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

    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        e = Event(pos=x, start=s - x, end=t - x)  
        events.append(e)
    events.sort(key=attrgetter('start'))
    events = deque(events)

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

    ans = [-1] * Q
    h = []
    for idx, d in enumerate(D):
        while events and events[0].start <= d:
            e = events.popleft()
            heappush(h, UC(pos=e.pos, end=e.end))

        while h and h[0].end <= d:
            heappop(h)

        if h:
            ans[idx] = h[0].pos

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


if __name__ == '__main__':
    main()

Solution (Python):


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

    input = sys.stdin.readline
    Event = namedtuple('Event', 'pos start end')
    UC = namedtuple('UC', 'pos end')  

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

    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        e = Event(pos=x, start=s - x, end=t - x)  
        events.append(e)
    events.sort(key=attrgetter('start'))
    events = deque(events)

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

    ans = []
    h = []
    for d in D:
        while events and events[0].start <= d:
            e = events.popleft()
            heappush(h, UC(pos=e.pos, end=e.end))

        while h and h[0].end <= d:
            heappop(h)

        ans.append(h[0].pos if h else -1)

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from bisect import bisect_left
    from collections import namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'pos start end')

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

    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        e = Event(pos=x, start=s - x, end=t - x)  
        events.append(e)
    events.sort(key=attrgetter('pos'))

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

    ans = [-1] * Q
    see = [-1] * Q
    for e in events:
        left = bisect_left(D, e.start)
        right = bisect_left(D, e.end)
        
        
        idx = left
        while idx < right:
            if ~ans[idx]:
                idx = see[idx]
                continue
            ans[idx] = e.pos
            see[idx] = right
            idx += 1
            
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
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)]
B = [-1 for j in range(q)]
for i in range(n):
    l = bisect.bisect_left(D, S[i]-X[i])
    r = bisect.bisect_left(D, T[i]-X[i])
    while l < r:
        if B[l] == -1:
            A[l] = X[i]
            B[l] = r
            l += 1
        else:
            l = B[l]
print(*A, sep='\n')

Solution (Python):
class BIT:
    def __init__(self, N):
        self.tree = [0] * (N + 1)  
        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()