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


from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class SegmentTree:  
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.lazy = [None] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        for i in range(self.n-1):
            self.query(i, i+1)
        return self.tree[self.N-1:self.n+self.N-1]

    def getindex(self, l, r):
        l = (l + self.N)
        r = (r + self.N)
        lm = l // (l & -l) >> 1
        rm = r // (r & -r) >> 1
        while r-l > 0:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l = l >> 1
            r = r >> 1
        while l:
            yield l
            l = l >> 1

    def propagates(self, *indices):
        for i in reversed(indices):
            i -= 1
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i+1] = self.tree[2*i+1] = v >> 1
            self.lazy[2*i+2] = self.tree[2*i+2] = v >> 1
            self.lazy[i] = None

    def update(self, p, q, x):
        if p == q:
            return None
        indices = tuple(self.getindex(p, q))
        self.propagates(*indices)
        p += self.N-1
        q += self.N-2
        while q-p > 0:
            if p % 2 == 0:
                self.lazy[p] = self.tree[p] = x
            if q % 2 == 1:
                self.lazy[q] = self.tree[q] = x
            p = p//2
            q = q//2 - 1
            x <<= 1
        if p == q:
            self.lazy[p] = self.tree[p] = x
        for i in indices:
            i -= 1
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def query(self, p, q):  
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        self.propagates(*self.getindex(p, q))
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 0:
            if p % 2 == 0:
                res = self.opr(res, self.tree[p])
            if q % 2 == 1:
                res = self.opr(res, self.tree[q])
            p = p//2
            q = q//2 - 1
        if p == q:
            res = self.opr(res, self.tree[p])
        return res


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

Works = []
for _ in range(n):
    s, t, x = map(int, input().split())
    Works.append((s, t, x))
Works = sorted(Works, key=lambda w: -w[2])

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

ST = SegmentTree([-1]*q)

for s, t, x in Works:
    left = bisect_left(People, s-x)
    right = bisect_left(People, t-x)
    ST.update(left, right, x)

for x in ST.values():
    print(x)

Solution (Python):


from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class SegmentTree:  
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.lazy = [None] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        return self.tree[self.N-1:self.n+self.N-1]

    def getindex(self, l, r):
        l = (l + self.N)
        r = (r + self.N)
        lm = l // (l & -l) >> 1
        rm = r // (r & -r) >> 1
        while r-l > 0:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l = l >> 1
            r = r >> 1
        while l:
            yield l
            l = l >> 1

    def propagates(self, *indices):
        for i in reversed(indices):
            i -= 1
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i+1] = self.tree[2*i+1] = v >> 1
            self.lazy[2*i+2] = self.tree[2*i+2] = v >> 1
            self.lazy[i] = None

    def update(self, p, q, x):
        if p == q:
            return None
        indices = tuple(self.getindex(p, q))
        self.propagates(*indices)
        p += self.N-1
        q += self.N-2
        while q-p > 0:
            if p % 2 == 0:
                self.lazy[p] = self.tree[p] = x
            if q % 2 == 1:
                self.lazy[q] = self.tree[q] = x
            p = p//2
            q = q//2 - 1
            x <<= 1
        if p == q:
            self.lazy[p] = self.tree[p] = x
        for i in indices:
            i -= 1
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def query(self, p, q):  
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        self.propagates(*self.getindex(p, q))
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 0:
            if p % 2 == 0:
                res = self.opr(res, self.tree[p])
            if q % 2 == 1:
                res = self.opr(res, self.tree[q])
            p = p//2
            q = q//2 - 1
        if p == q:
            res = self.opr(res, self.tree[p])
        return res


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

Works = []
for _ in range(n):
    s, t, x = map(int, input().split())
    Works.append((s, t, x))
Works = sorted(Works, key=lambda w: -w[2])

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

ST = SegmentTree([-1]*q)

for s, t, x in Works:
    left = bisect_left(People, s-x)
    right = bisect_left(People, t-x)
    ST.update(left, right, x)

for i in range(q):
    print(ST.query(i, i+1))

Solution (Python):
import heapq
class HeapDict:
    def __init__(self):
        self.h = []
        self.d = {}

    def insert(self,x):
        if x not in self.d or self.d[x] == 0:
            heapq.heappush(self.h, x)
        self.d.setdefault(x,0)
        self.d[x] += 1


    def erase(self,x):
        if x not in self.d or self.d[x] == 0:
            return
        else:
            self.d[x] -= 1

        while self.h:
            if self.d[self.h[0]] == 0:
                heapq.heappop(self.h)
            else:
                break


    def get_min(self):
        if not self.h:
            return None
        else:
            return self.h[0]


    def pop(self):
        poped_val = self.h[0]
        self.erase(poped_val)
        return poped_val


    def exist(self, x):
        return (x in self.d and self.d[x] > 0)


    def show_h(self):
        elems = [v for v in self.h if self.d[v] > 0]
        print(elems)


    def show_d(self):
        print(self.d)



def main():
    n,q = map(int, input().split())
    eventl = []

    for _ in range(n):
        s,t,x = map(int, input().split())
        eventl.append((s-x, 'a-stop', x)) 
        eventl.append((t-x, 'b-start', x))

    for i in range(q):
        d = int(input())
        eventl.append((d,'c-go', i))

    eventl.sort()

    ans = [0]*q
    hd = HeapDict()
    for e in eventl:
        if e[1] == 'a-stop':
            hd.insert(e[2])
        elif e[1] == 'b-start':
            hd.erase(e[2])
        else:
            min_x = hd.get_min()
            if min_x is not None:
                ans[e[2]] = min_x
            else:
                ans[e[2]] = -1

    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
class HeapDict:
    def __init__(self):
        self.h = []
        self.d = {}

    def insert(self,x):
        if x not in self.d or self.d[x] == 0:
            heapq.heappush(self.h, x)
        self.d.setdefault(x,0)
        self.d[x] += 1


    def erase(self,x):
        if x not in self.d or self.d[x] == 0:
            return
        else:
            self.d[x] -= 1

        while self.h:
            if self.d[self.h[0]] == 0:
                heapq.heappop(self.h)
            else:
                break


    def get_min(self):
        if not self.h:
            return None
        else:
            return self.h[0]


    def pop(self):
        poped_val = self.h[0]
        self.erase(poped_val)
        return poped_val


    def exist(self, x):
        return (x in self.d and self.d[x] > 0)


    def show_h(self):
        elems = [v for v in self.h if self.d[v] > 0]
        print(elems)


    def show_d(self):
        print(self.d)




n,q = map(int, input().split())
eventl = []

for _ in range(n):
    s,t,x = map(int, input().split())
    eventl.append((s-x, 'a-stop', x)) 
    eventl.append((t-x, 'b-start', x))

for i in range(q):
    d = int(input())
    eventl.append((d,'c-go', i))

eventl.sort()

ans = [0]*q
hd = HeapDict()
for e in eventl:
    if e[1] == 'a-stop':
        hd.insert(e[2])
    elif e[1] == 'b-start':
        hd.erase(e[2])
    else:
        min_x = hd.get_min()
        if min_x is not None:
            ans[e[2]] = min_x
        else:
            ans[e[2]] = -1

for a in ans:
    print(a)

Solution (Python):
import heapq
class HeapDict:
    def __init__(self):
        self.h = []
        self.d = {}

    def insert(self,x):
        if x not in self.d or self.d[x] == 0:
            heapq.heappush(self.h, x)
        self.d.setdefault(x,0)
        self.d[x] += 1


    def erase(self,x):
        if x not in self.d or self.d[x] == 0:
            return
        else:
            self.d[x] -= 1

        while self.h:
            if self.d[self.h[0]] == 0:
                heapq.heappop(self.h)
            else:
                break


    def get_min(self):
        if not self.h:
            return None
        else:
            return self.h[0]


    def pop(self):
        poped_val = self.h[0]
        self.erase(poped_val)
        return poped_val


    def exist(self, x):
        return (x in self.d and self.d[x] > 0)


    def show_h(self):
        elems = [v for v in self.h if self.d[v] > 0]
        print(elems)


    def show_d(self):
        print(self.d)




n,q = map(int, input().split())
eventl = []

for _ in range(n):
    s,t,x = map(int, input().split())
    eventl.append((s-x, 'a-stop', x)) 
    eventl.append((t-x, 'b-start', x))

for i in range(q):
    d = int(input())
    eventl.append((d,'c-go', i))

eventl.sort()

ans = [0]*q
hd = HeapDict()
for e in eventl:
    if e[1] == 'a-stop':
        hd.insert(e[2])
    elif e[1] == 'b-start':
        hd.erase(e[2])
    else:
        min_x = hd.get_min()
        if min_x is not None:
            ans[e[2]] = min_x
        else:
            ans[e[2]] = -1

for a in ans:
    print(a)

Solution (Python):
import heapq, sys
input = sys.stdin.readline
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))

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

event.sort(key=lambda x: (x[0], x[1]))
now = []
memo = set()

tmp = 0

for i, (t, flg, x) in enumerate(event):
    if flg == -1:
        memo.remove(x)
    elif flg == 1:
        heapq.heappush(now, x)
        memo.add(x)
    else:
        while len(now) > 0 and now[0] not in memo:
            heapq.heappop(now)
        if len(now) > 0:
            print(now[0])
        else:
            print(-1)

Solution (Python):
from bisect import*
b=bisect_left
n,q,*t=map(int,open(0).read().split())
p=t[-q:]
*a,=o=[-1]*q
for x,t,s in sorted(zip(*[iter(t[~q::-1])]*3)):
 l,r=b(p,s-x),b(p,t-x)
 while l<r:
  if~o[l]:l=o[l]
  else:a[l],o[l]=x,r;l+=1
print(*a)

Solution (Python):
import bisect
 
 
class SegTree:
 
    def __init__(self, n):
        
        self.n = n
        self.val = [-1] * (2 * n - 1)
 
    def _update(self, a, b, v, k, l, r):
        
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)
 
    def query(self, x):
        
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret
 
 
def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for n in range(N)] 
    
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [int(input()) for q in range(Q)]
    
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree._update(left, right, w, 0, 0, QQ)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])
 
 
if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop

N, Q = map(int, input().split())
l, q = [], []
u = set()

for _ in range(N):
    S, T, X = map(int, input().split())
    l += [(S-X, 1, X), (T-X, 0, X)]
for i in range(Q):
    l += [(int(input()), 2, i)]
l.sort()

for _, m, x in l:
    if m==0:
        u.remove(x)
    elif m==1:
        heappush(q, x)
        u.add(x)
    else:
        while q:
            if q[0] not in u:
                heappop(q)
            else:
                break
        print(q[0] if q else -1)

Solution (Python):
from heapq import heappush, heappop

N, Q = map(int, input().split())
l, q = [], []
u = set()

for _ in range(N):
    S, T, X = map(int, input().split())
    l.append((S-X, 1, X))
    l.append((T-X, 0, X))

for i in range(Q):
    l.append((int(input()), 2, i))

l.sort()

for _, m, x in l:
    if m==0:
        u.remove(x)
    elif m==1:
        heappush(q, x)
        u.add(x)
    else:
        while q:
            if q[0] not in u:
                heappop(q)
            else:
                break
        print(q[0] if q else -1)

Solution (Python):
from heapq import heappush, heappop

N, Q = map(int, input().split())
l = []
used = set()
q = []

for i in range(N):
    S, T, X = map(int, input().split())
    l.append((S-X, 1, X))
    l.append((T-X, 0, X))

for i in range(Q):
    l.append((int(input()), 2, i))

l.sort()

for pos, m, x in l:
    if m==0:
        used.remove(x)
    elif m==1:
        heappush(q, x)
        used.add(x)
    else:
        while q:
            if q[0] not in used:
                heappop(q)
            else:
                break
        print(q[0] if q else -1)

Solution (Python):
from heapq import heappush, heappop

N, Q = map(int, input().split())
l = []
ans = [0]*Q
used = set()
q = []

for i in range(N):
    S, T, X = map(int, input().split())
    l.append((S-X, 1, X))
    l.append((T-X, 0, X))

for i in range(Q):
    v = int(input())
    l.append((v, 2, i))

l.sort()

for pos, m, x in l:
    if m==0:
        used.remove(x)
    elif m==1:
        heappush(q, x)
        used.add(x)
    else:
        while q:
            if q[0] not in used:
                heappop(q)
            else:
                break
        ans[x] = q[0] if q else -1

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

Solution (Python):

import sys
from bisect import bisect_left, bisect_right
import heapq

INF = float("inf")


class ErasableHeap(object):
    
    def __init__(self):
        self.data = []
        self.event = []

    def push(self, x):
        return heapq.heappush(self.data, x)

    def erase(self, x):
        return heapq.heappush(self.event, x)

    def _check(self):
        while self.event and\
                self.data[0] == self.event[0]:
            heapq.heappop(self.data)
            heapq.heappop(self.event)

    def front(self):
        self._check()
        return self.data[0]

    def pop(self):
        self.check()
        return heapq.heappop(self.data)

    def __len__(self):
        self._check()
        return len(self.data)


def main():

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

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

    head = 0
    stack = ErasableHeap()
    for t, p, x in event:
        while head < Q and D[head] < t:
            if len(stack) == 0:
                print(-1)
            else:
                print(stack.front())
            head += 1
        if p == 1:
            stack.push(x)
        else:
            stack.erase(x)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from bisect import bisect_left, bisect_right
import heapq

INF = float("inf")


class ErasableHeap(object):
    
    def __init__(self):
        self.data = []
        self.event = []

    def push(self, x):
        return heapq.heappush(self.data, x)

    def erase(self, x):
        return heapq.heappush(self.event, x)

    def _check(self):
        while self.event and\
                self.data[0] == self.event[0]:
            heapq.heappop(self.data)
            heapq.heappop(self.event)

    def front(self):
        self._check()
        return self.data[0]

    def pop(self):
        self.check()
        return heapq.heappop(self.data)

    def __len__(self):
        self._check()
        return len(self.data)


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

    event.sort()

    head = 0
    stack = ErasableHeap()
    for t, p, x in event:
        while D[head] < t:
            if len(stack) == 0:
                print(-1)
            else:
                print(stack.front())
            head += 1
            if head >= Q:
                return
        if p == 1:
            stack.push(x)
        else:
            stack.erase(x)

    while head < len(D):
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.front())
        head += 1
        if head >= Q:
            return


if __name__ == '__main__':
    main()

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

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


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    pos_set = set()
    pos_hq = []
    ans = []
    for _, com, pos in events:
        if com == 0:
            pos_set.remove(pos)
        elif com == 1:
            pos_set.add(pos)
            heappush(pos_hq, pos)
        else:
            while pos_hq:
                if pos_hq[0] not in pos_set:
                    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):
import sys
from operator import itemgetter

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


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        
        self.data[k] = x
        
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        
        return res


def solve():
    N, Q = map(int, rl().split())
    events = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
        xs.add(x)
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    x_to_idx = {x: idx for idx, x in enumerate(sorted(xs))}
    M = len(xs)
    ide_ele = 10 ** 10
    seg_tree = SegmentTree([ide_ele] * M, min, ide_ele)
    
    ans = []
    for _, com, pos in events:
        if com == 0:
            seg_tree.update(x_to_idx[pos], ide_ele)
        elif com == 1:
            seg_tree.update(x_to_idx[pos], pos)
        else:
            tmp = seg_tree.data[0]
            ans.append(tmp if tmp != ide_ele else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append((s-x, x, 1))
    E.append((t-x, x, -1))
E.append((10**10, 10**10, 1))

E.sort()



from heapq import heappush, heappop
Q = []

j = 0
for i in range(q):
    
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] += 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] -= 1
        j += 1
    
    while len(Q) > 0 and F[Q[0]] == 0:
        _ = heappop(Q)
    if len(Q) == 0:
        print(-1)
    else:
        print(Q[0])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()

event = [None]*(2*N+Q)
Xl = [0]*N
for i in range(N):
    S, T, X = MAP()
    event[2*i] = (S-X, 1, X)
    event[2*i+1] = (T-X, 0, X)
    Xl[i] = X

t = 2*N
for i in range(Q):
    D = INT()
    event[t+i] = (D, 2, 0)


event.sort()
p = []
q = []
for t, c, x in event:
    if c == 0:
        heappush(q, x)
    elif c == 1:
        heappush(p, x)
    else:
        while q and p[0] == q[0]:
            heappop(p)
            heappop(q)
        print(-1 if not p else p[0])

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
append = event.append
for s, t, x in STX:
    append((s-x, 0, x))
    append((t-x, -1, x))

for i in range(Q):
    d = ir()
    append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

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

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
append = event.append
for s, t, x in STX:
    append((s-x, 0, x))
    append((t-x, -1, x))

for i in range(Q):
    d = ir()
    append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
add = cur.add
remove = cur.remove
for a, b, c in event:
    if b == 0:
        add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

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

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
STX.sort(key=lambda x: x[2], reverse=True)
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

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

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

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

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

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