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
input = sys.stdin.readline
from bisect import bisect_left
inf = float('inf')

class SegmentTree:
    def __init__(self, N):
        tmp = 1
        while tmp < N:
            tmp <<= 1
        self.N = tmp
        self.data = [inf for _ in range(2*self.N-1)]
    
    def update(self, l, r, x):
        L = l + self.N - 1
        R = r + self.N - 1
        while L < R:
            if R & 1:
                R -= 1
                self.data[R] = min(self.data[R], x)
            if L & 1:
                self.data[L] = min(self.data[L], x)
                L += 1
            L >>= 1; R >>= 1
    
    def value(self, k):
        k += self.N - 1
        res = self.data[k]
        while k != 0:
            k >>= 1
            res = min(res, self.data[k])
        return res

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

st = SegmentTree(Q)
for S, T, X in STX:
    l = bisect_left(D, S-X)
    r = bisect_left(D, T-X)
    st.update(l, r, X)

for k in range(Q):
    ans = st.value(k)
    if ans == inf:
        ans = -1
    print(ans)

Solution (Python):
from bisect import bisect_left


def main():
    N, Q, *I = map(int, open(0).read().split())
    STX, D = I[:3 * N], I[3 * N:]

    E = sorted(zip(*[iter(STX)] * 3), key=lambda x: x[2])

    R = [-1] * Q
    ans = [-1] * Q

    for s, t, x in E:
        l = bisect_left(D, s - x)
        r = bisect_left(D, t - x)
        while l < r:
            if R[l] == -1:
                ans[l] = x
                R[l] = r
                l += 1
            else:
                l = R[l]

    print("\n".join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left


def main():
    N, Q, *I = map(int, open(0).read().split())
    STX, D = I[:3 * N], I[3 * N:]

    E = sorted(zip(*[iter(STX)] * 3), key=lambda x: x[2])

    R = [-1] * Q
    ans = [-1] * Q

    for s, t, x in E:
        l = bisect_left(D, s - x)
        r = bisect_left(D, t - x)
        while l < r:
            if R[l] == -1:
                ans[l] = x
                R[l] = r
                l += 1
            else:
                l = R[l]

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left
inf = float('inf')

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

res = 1
while res < Q:
    res <<= 1
N0 = res
data = [inf for _ in range(2*N0-1)]

def update(l, r, x):
    L = l + N0
    R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R] = min(data[R], x)
        if L & 1:
            data[L] = min(data[L], x)
            L += 1
        L >>= 1; R >>= 1

def value(k):
    k += N0
    res = data[k]
    while k != 0:
        k >>= 1
        res = min(res, data[k])
    return res


for S, T, X in STX:
    l = bisect_left(D, S-X)
    r = bisect_left(D, T-X)
    update(l, r, X)

for k in range(Q):
    ans = value(k)
    if ans == inf:
        ans = -1
    print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
stx = [LI() for _ in range(n)]
stx.sort(key = itemgetter(2))
d = [I() for _ in range(q)]
ans = [-1]*q
skip = [-1]*q
for s,t,x in stx:
    l,r = bl(d,s-x),bl(d,t-x)
    while l < r:
        if skip[l] == -1:
            skip[l] = r
            ans[l] = x
            l += 1
        else:
            l = skip[l]
print(*ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
stx = [LI() for _ in range(n)]
stx.sort(key = itemgetter(2))
d = [I() for _ in range(q)]
ans = [-1]*(q+1)
right = [0]*q
for s,t,x in stx:
    l,r = bl(d,s-x),bl(d,t-x)
    
    
    while l < r:
        while ans[l] != -1:
            l = right[l]
        if r <= l:
            break
        ans[l] = x
        right[l] = r
        l += 1
for i in ans[:-1]:
    print(i)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop
from collections import defaultdict

N,Q = map(int,readline().split())
data = list(map(int,read().split()))
S = data[:3*N:3]
T = data[1:3*N:3]
X = data[2:3*N:3]
D = data[3*N:]

event = []
event += [(s-x,1,x) for x,s in zip(X,S)] 
event += [(t-x,2,x) for x,t in zip(X,T)] 
event += [(x,3,i) for i,x in enumerate(D)] 

event.sort()

INF = 10**10
q = [INF]
counter = defaultdict(int)
counter[INF] = 1

answer = [None] * Q
for a,b,c in event:
    if b == 1:
        heappush(q,c)
        counter[c] += 1
    elif b == 2:
        counter[c] -= 1
    else:
        while counter[q[0]] == 0:
            heappop(q)
        x = q[0]
        if x == INF:
            x = -1
        answer[c] = x

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

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


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    
    def bisect_plus(self, i, t):
        L = i
        R = self.size
        R_prev = R
        sum_i = self.sum(i)
        while True:
            range_sum = self.sum(R) - sum_i
            if range_sum < t:
                if R == self.size:
                    return self.size + 1
                L, R = R, R_prev
            else:
                R_prev = R
                R = (L + R + 1) // 2
                if R == R_prev:
                    return R

    
    def bisect_minus(self, i, t):
        L = 1
        R = i
        L_prev = L
        sum_i = self.sum(i - 1)
        while True:
            range_sum = sum_i - self.sum(L - 1)
            if range_sum < t:
                if L == 1:
                    return 0
                L, R = L_prev, L
            else:
                L_prev = L
                L = (L + R) // 2
                if L == L_prev:
                    return L


def main():
    N, Q = map(int, input().split())
    ev = []
    x_list = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        ev.append([s-x, 1, x])
        ev.append([t-x, -1, x])
        x_list.append(x)
    for _ in range(Q):
        d = int(input())
        ev.append([d, 0, 0])
    ev.sort(key=lambda p: p[0])
    x_list.sort()
    x_idx = {}
    for i in range(1, N+1):
        x_idx[x_list[i-1]] = i

    bit = Bit(N)
    x_list.append(-1)
    for pos, flag, x in ev:
        if flag == 0:
            print(x_list[bit.bisect_plus(0, 1) - 1])
        else:
            idx = x_idx[x]
            bit.add(idx, flag)


if __name__ == '__main__':
    main()

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

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n,q=map(int,input().split())
import heapq
S=[]
D=dict()
for i in range(n):
  s,t,x=map(int,input().split())
  S.append((1,x,max(0,s-x)))
  S.append((-1,x,max(0,t-x)))
  D[x]=False
S.sort(key=lambda x:x[2])
X=[]
cur=0
for i in range(q):
  d=int(input())
  while cur<2*n:
    a,b,c=S[cur]
    if c>d:
      break
    else:
      cur+=1
      if a==1:
        heapq.heappush(X,b)
        D[b]=True
      else:
        D[b]=False
  while X:
    ans=heapq.heappop(X)
    if D[ans]:
      print(ans)
      heapq.heappush(X,ans)
      break
  if not X:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
import heapq
S=[]
D=dict()
for i in range(n):
  s,t,x=map(int,input().split())
  S.append((1,x,max(0,s-x)))
  S.append((-1,x,max(0,t-x)))
  D[x]=False
S.sort(key=lambda x:x[2])
X=[]
cur=0
for i in range(q):
  d=int(input())
  while cur<2*n:
    a,b,c=S[cur]
    if c>d:
      break
    else:
      cur+=1
      if a==1:
        heapq.heappush(X,b)
        D[b]=True
      else:
        D[b]=False
  while X:
    ans=heapq.heappop(X)
    if D[ans]:
      print(ans)
      heapq.heappush(X,ans)
      break
  if not X:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n,q=map(int,input().split())
import heapq
S=[]
D=dict()
for i in range(n):
  s,t,x=map(int,input().split())
  S.append((1,x,max(0,s-x)))
  S.append((-1,x,max(0,t-x)))
  D[x]=False
S.sort(key=lambda x:x[2])
X=[]
cur=0
for i in range(q):
  d=int(input())
  while cur<2*n:
    a,b,c=S[cur]
    if c>d:
      break
    else:
      cur+=1
      if a==1:
        heapq.heappush(X,b)
        D[b]=True
      else:
        D[b]=False
  while X:
    ans=heapq.heappop(X)
    if D[ans]:
      print(ans)
      heapq.heappush(X,ans)
      break
  if not X:
    print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
import heapq
S=[]
D=dict()
for i in range(n):
  s,t,x=map(int,input().split())
  S.append((1,x,max(0,s-x)))
  S.append((-1,x,max(0,t-x)))
  D[x]=False
S.sort(key=lambda x:x[2])
X=[]
cur=0
for i in range(q):
  d=int(input())
  while cur<2*n:
    a,b,c=S[cur]
    if c>d:
      break
    else:
      cur+=1
      if a==1:
        heapq.heappush(X,b)
        D[b]=True
      else:
        D[b]=False
  while X:
    ans=heapq.heappop(X)
    if D[ans]:
      print(ans)
      heapq.heappush(X,ans)
      break
  if not X:
    print(-1)

Solution (Python):


import sys
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()


events = []
for i in range(N):
    s, t, x = MAP()
    
    events.append((s-x, 1, x))
    
    events.append((t-x, 0, x))
for i in range(Q):
    d = INT()
    
    events.append((d, 2, i))

events.sort()


S = set()
hp = []
ans = [0] * Q
for t, flag, x in events:
    
    if flag == 0:
        S.remove(x)
    
    elif flag == 1:
        S.add(x)
        heappush(hp, x)
    
    elif flag == 2:
        
        while len(hp) and hp[0] not in S:
            heappop(hp)
        if len(hp):
            ans[x] = hp[0]
        else:
            ans[x] = -1
[print(a) for a in ans]

Solution (Python):

import sys
input = sys.stdin.readline

from bisect import bisect_left

n,q = map(int, input().split())
road = [list(map(int, input().split())) for i in range(n)]
road.sort(key=lambda x: x[2])
start = [int(input()) for i in range(q)]

skip = [-1]*q
ans = [-1]*q
for s,t,x in road:
    left = bisect_left(start, s-x)
    right = bisect_left(start, t-x)
    
    
    while left < right:
        if skip[left] == -1:
            ans[left] = x
            skip[left] = right
            left += 1
        else:
            left = skip[left]
print(*ans, sep="\n")

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

class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.INF = float("inf")
        self.data = [self.INF]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] = v
            if l&1:
                self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] < res:
                res = self.data[i]
            i = ~-i//2
        return res

n,q = map(int, input().split())
start = [None]*q
se = set()

road = []
for i in range(n):
    s,t,x = map(int, input().split())
    road.append([x, x-t, x-s])
for i in range(q):
    d = int(input())
    start[i] = -d

start = start[::-1]

RUQ = RangeUpdateQuery(q)
road.sort(reverse=True)
from bisect import bisect_left,bisect_right
for i, (x, s, t) in enumerate(road):
    l = bisect_right(start, s)
    r = bisect_right(start, t)
    
    RUQ.update(l, r, x)

ans = []
for i in range(q):
    x = RUQ.query(i)
    if x == float("inf"):
        x = -1
    ans.append(x)
ans = ans[::-1]
print(*ans, sep="\n")

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))



from operator import itemgetter
from bisect import bisect_left

class Range_SegmentTree:
    def __init__(self,N):
        self.N0 = 2**(N-1).bit_length()
        self.tree = [None]*(2*self.N0)    
        self.INF = (-1, 2**31-1)

    
    
    def update(self,l,r,v):
        L = l + self.N0; R = r + self.N0 + 1
        while L < R:
            if R & 1:
                R -= 1
                self.tree[R-1] = v
            if L & 1:
                self.tree[L-1] = v
                L += 1
            L >>= 1; R >>= 1

    
    def _query(self,k):
        k += self.N0-1
        s = self.INF
        while k >= 0:
            if self.tree[k]:
                s = max(s, self.tree[k])
            k = (k - 1) // 2
        return s

    
    def query(self,k):
        return self._query(k)[1]
      
N,Q = II()
a = []
for _ in range(N):
    s,t,x = II()
    a.append((x, s-x-0.5, t-x-0.5))
D = Line(Q,1)
 
a.sort(key=itemgetter(0),reverse=True)
 
seg = Range_SegmentTree(Q)
for i,b in enumerate(a):
    l = bisect_left(D,b[1])
    r = bisect_left(D,b[2])
    seg.update(l,r-1,(i,b[0]))
    
for i in range(Q):
    x = seg.query(i)
    if x == 2**31-1:
        print(-1)
    else:
        print(x)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))



from operator import itemgetter
from bisect import bisect_left

N,Q = II()
a = []
for _ in range(N):
    s,t,x = II()
    a.append((x, s-x-0.5, t-x-0.5))
a.sort(key=itemgetter(0))
D = Line(Q,1)

ans = [-1]*(Q+1)
right = [0]*Q
for a0 in a:
    l = bisect_left(D,a0[1])
    r = bisect_left(D,a0[2])
    while l<r:
        while ans[l]!=-1:
            l = right[l]
            if l==N:
                break
        if l>=r:
            break
        ans[l] = a0[0]
        right[l] = r
        l += 1

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

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
INF = float('inf')

class SegmentTree:

    def __init__(self, N):
        self.N = 1<<(N-1).bit_length()
        self.data = [None] * (2*self.N)

    def Update(self, l, r, t, v):
        L, R, val = l+self.N, r+self.N, (t, v)
        while L < R:
            if R & 1:
                R -= 1
                self.data[R-1] = val
            if L & 1:
                self.data[L-1] = val
                L += 1
            L >>= 1
            R >>= 1

    def getValue(self, x):
        x += self.N-1
        ret = (-1, INF)
        while x >= 0:
            if self.data[x]:
                ret = max(ret, self.data[x])
            x = (x-1)//2
        return ret[1]

N, Q = map(int, input().split())
stx = [[int(x) for x in input().split()] for i in range(N)]
stx.sort(key = lambda v : -v[2])
D = [(int(input()), i) for i in range(Q)]
D.sort(key = lambda v : v[0])
d, p = [d for d, p in D], [p for d, p in D]
seg = SegmentTree(Q)
for i, (s, t, x) in enumerate(stx):
    l = bisect_left(d, s-x)
    r = bisect_left(d, t-x)
    seg.Update(l, r, i, x)
ans = [None] * Q
for i in range(Q):
    tmp = seg.getValue(i)
    if tmp == INF:
        tmp = -1
    ans[p[i]] = tmp
print(*ans, sep = '\n')

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
INF = 10 ** 18

from collections.abc import Sequence, Set
from bisect import bisect_left
from itertools import chain

from heapq import heappush, heappop

class HeapSet():
    
    def __init__(self):
        self._set = set()
        self._list = list()

    def add(self, a):
        if a in self._set:
            return
        else:
            self._set.add(a)
            heappush(self._list, a)

    def remove(self, a):
        if a not in self._set:
            raise ValueError
        else:
            self._set.remove(a)

    def peek(self):
        if not self._set:
            self._list = list()
            raise IndexError
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        return a

    def pop(self):
        a = self.peek()
        self._set.remove(a)
        heappop(self._list)
        return a


    def get_set(self): return self._set
    def get_heapq(self): return self._list
    def get_list(self): return self._list
    def __bool__(self): return True if self._set else False
    def __contains__(self, a): return a in self._set
    def __len__(self): return len(self._set)
    def __repr__(self): return "HeapSet(" + (repr(self._set) if self._set else '') + ")"





def main(): 
    N, Q = LI()
    events = []
    for _ in range(N):
        stx = LI()
        
        
        events.append((stx[0] - stx[2], stx[2], True))  
        events.append((stx[1] - stx[2], stx[2], False))  
    for _ in range(Q):
        events.append((II(), INF, -1))
 
    
    events.sort()  
 
    from array import array
    ans = array('i')
    
    m = HeapSet()
    
    change_flag = True
    min_ = INF
    for txa in events:
        if txa[2] == -1:
            if not m:
                ans.append(-1)
                
            else:
                if change_flag:
                    min_ = m.peek()
                    change_flag = False
                ans.append(min_)
                
        elif txa[2]:
            m.add(txa[1])
            if txa[1] < min_:
                min_ = txa[1]
                change_flag = False
        else:
            m.remove(txa[1])
            if txa[1] == min_ and m:
                min_ = m.peek()
                change_flag = False
            elif not m:
                min_ = INF
                change_flag = False
 
    
    
    print('\n'.join(map(str, ans.tolist())))


main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
INF = 10 ** 18

from collections.abc import Sequence, Set
from bisect import bisect_left
from itertools import chain

from heapq import heappush, heappop

class HeapSet():
    
    def __init__(self):
        self._set = set()
        self._list = list()

    def add(self, a):
        if a in self._set:
            return
        else:
            self._set.add(a)
            heappush(self._list, a)

    def remove(self, a):
        if a not in self._set:
            raise ValueError
        else:
            self._set.remove(a)

    def pop(self):
        if not self._set:
            self._list = list()
            raise IndexError
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        self._set.remove(a)
        return a

    def peek(self):
        if not self._set:
            self._list = list()
            raise IndexError
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        return a

    def get_set(self): return self._set
    def get_heapq(self): return self._list
    def get_list(self): return self._list
    def __bool__(self): return True if self._set else False
    def __contains__(self, a): return a in self._set
    def __len__(self): return len(self._set)
    def __repr__(self):
        return "HeapSet(" + (repr(self._set) if self._set else '') + ")"





def main(): 
    N, Q = LI()
    events = []
    for _ in range(N):
        stx = LI()
        
        
        events.append((stx[0] - stx[2], stx[2], True))  
        events.append((stx[1] - stx[2], stx[2], False))  
    for _ in range(Q):
        events.append((II(), INF, -1))
 
    
    events.sort()  
 
    from array import array
    ans = array('i')
    
    m = HeapSet()
    
    change_flag = True
    min_ = INF
    for txa in events:
        if txa[2] == -1:
            if not m:
                ans.append(-1)
                
            else:
                if change_flag:
                    min_ = m.peek()
                    change_flag = False
                ans.append(min_)
                
        elif txa[2]:
            m.add(txa[1])
            if txa[1] < min_:
                min_ = txa[1]
                change_flag = False
        else:
            m.remove(txa[1])
            if txa[1] == min_ and m:
                min_ = m.peek()
                change_flag = False
            elif not m:
                min_ = INF
                change_flag = False
 
    
    
    print('\n'.join(map(str, ans.tolist())))

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
INF = 10 ** 18

from collections.abc import Sequence, Set
from bisect import bisect_left
from itertools import chain

from heapq import heappush, heappop

class HeapqSet():
    def __init__(self):
        self._set = set()
        self._list = list()

    def add(self, a):
        if a in self._set:
            return
        else:
            self._set.add(a)
            heappush(self._list, a)

    def remove(self, a):
        if a not in self._set:
            raise ValueError
        else:
            self._set.remove(a)

    def pop_min(self):
        if not self._set:
            self._list = list()
            return None
        while True:
            a = heappop(self._list)
            if a not in self._set:
                continue
            else:
                self._set.remove(a)
                break
        return a

    def peek_min(self):
        if not self._set:
            self._list = list()
            return None
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        return a

    def is_empty(self):
        return not self._set

    def __bool__(self):
        return True if self._set else False





def main(): 
    N, Q = LI()
    events = []
    for _ in range(N):
        stx = LI()
        
        
        events.append((stx[0] - stx[2], stx[2], True))  
        events.append((stx[1] - stx[2], stx[2], False))  
    for _ in range(Q):
        events.append((II(), INF, -1))
 
    
    events.sort()  
 
    from array import array
    ans = array('i')
    
    m = HeapqSet()
    
    change_flag = True
    min_ = INF
    for txa in events:
        if txa[2] == -1:
            if not m:
                ans.append(-1)
                
            else:
                if change_flag:
                    min_ = m.peek_min()
                    change_flag = False
                ans.append(min_)
                
        elif txa[2]:
            m.add(txa[1])
            if txa[1] < min_:
                min_ = txa[1]
                change_flag = False
        else:
            m.remove(txa[1])
            if txa[1] == min_ and m:
                min_ = m.peek_min()
                change_flag = False
            elif not m:
                min_ = INF
                change_flag = False
 
    
    
    print('\n'.join(map(str, ans.tolist())))



main()

Solution (Python):


import sys
input = sys.stdin.readline

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

stx=sorted(stx,key=lambda x:x[2])

ans=[-1 for _ in range(q)]
skip=[-1 for _ in range(q)]

from bisect import bisect_left

for s,t,x in stx:
	left=bisect_left(d,s-x)
	right=bisect_left(d,t-x)
	while left<right:
		if skip[left]==-1:
			ans[left]=x
			skip[left]=right
			left+=1
		else:
			left=skip[left]
print('\n'.join(map(str,ans)))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left

    N, Q = map(int, input().split())
    c = []
    c_append = c.append
    for _ in range(N):
        s, t, x = map(int, input().split())
        c_append((x, s, t))
    c.sort()

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

    ans = [-1] * Q
    skip = [-1] * Q

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

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

if __name__ == '__main__':
    main()

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

    N, Q = map(int, input().split())
    used = defaultdict(int)
    tank = []
    
    p = []
    p_append = p.append
    for i in range(N):
        s, t, x = map(int, input().split())
        p_append((s - x, x))
        p_append((t - x, -x))
    p.sort()

    cnt = 0
    for i in range(Q):
        d = int(input())
        while cnt <= len(p) - 1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w >= 0:
                used[w] += 1
                heappush(tank, w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print (-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print (kouho)
                break
            else:
                heappop(tank)

if __name__ == '__main__':
    main()