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

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math
import heapq


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


# n : kouji count
def main():
    n, q = intin()
    stxlist = intinl(n)
    dlist = intinl(q)

    stxlist = [(s - x, t - x, x) for s, t, x in stxlist]

    event_list = []
    for s, t, x in stxlist:
        event_list.append((s, 1, x))
        event_list.append((t, -1, x))
    event_list.append((float('inf'), 1, -1))

    event_list.sort()

    stop_list = []
    remove_dict = defaultdict(int)
    event_idx = 0
    d_idx = 0

    while True:
        time, event, x = event_list[event_idx]
        event_idx += 1

        while d_idx < q and dlist[d_idx] < time:
            d = dlist[d_idx]
            d_idx += 1

            while stop_list and remove_dict[stop_list[0]]:
                remove_dict[stop_list[0]] -= 1
                heapq.heappop(stop_list)
            if stop_list:
                print(stop_list[0])
            else:
                print(-1)

            if d_idx >= q:
                return

        if event == 1:
            heapq.heappush(stop_list, x)
        if event == -1:
            remove_dict[x] += 1


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math
import heapq


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


# n : kouji count
def main():
    n, q = intin()
    stxlist = intinl(n)
    dlist = intinl(q)

    stxlist = [(s - x, t - x, x) for s, t, x in stxlist]

    event_list = []
    for s, t, x in stxlist:
        event_list.append((s, 1, x))
        event_list.append((t, -1, x))

    for d in dlist:
        event_list.append((d, 2, 0))

    event_list.sort()

    stop_list = []
    remove_dict = defaultdict(int)
    for time, event, x in event_list:
        if event == 2:
            while stop_list and remove_dict[stop_list[0]]:
                remove_dict[stop_list[0]] -= 1
                heapq.heappop(stop_list)
            if stop_list:
                print(stop_list[0])
            else:
                print(-1)
        if event == 1:
            heapq.heappush(stop_list, x)
        if event == -1:
            remove_dict[x] += 1


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math
import heapq


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


# n : kouji count
def main():
    n, q = intin()
    stxlist = intinl(n)
    dlist = intinl(q)

    stxlist = [(s - x, t - x, x) for s, t, x in stxlist]

    event_list = []
    for s, t, x in stxlist:
        event_list.append((s, 1, x))
        event_list.append((t, -1, x))

    for d in dlist:
        event_list.append((d, 2, 0))

    event_list.sort()

    stop_list = []
    remove_dict = defaultdict(int)
    for time, event, x in event_list:
        if event == 2:
            if stop_list:
                print(stop_list[0])
            else:
                print(-1)
        if event == 1:
            heapq.heappush(stop_list, x)
        if event == -1:
            remove_dict[x] += 1
            while stop_list and remove_dict[stop_list[0]]:
                remove_dict[stop_list[0]] -= 1
                heapq.heappop(stop_list)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapでソートを保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

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

Submission status: Time Limit Exceeded

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

event = []
spot_set = set()
for stop in stops:
    d = stop[2]
    start = stop[0] - d
    finish = stop[1] - d
    event.append([start, 1, d])
    event.append([finish, -1, d])

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

for i in range(len(event)):
    e = event[i]
    if e[1] == 1:
        spot_set.add(e[2])
    else:
        spot_set.remove(e[2])
    while len(D) > 0 and i < len(event)-1 and D[0] < event[i+1][0]:
        if len(spot_set) > 0:
            print(min(spot_set))
        else:
            print("-1")
        D.pop(0)

for d in D:
    print("-1")

Submission status: Time Limit Exceeded

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

num, person = map(int, input().split())
arr = []

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

for i in range(person):
    d = int(input())
    arr.append((d,))

arr.sort()

heap = []
done = set()

for elem in arr:
    if len(elem) == 1:
        while heap and heap[0][1] in done:
            heappop(heap)
        if heap:
            print(heap[0][0])
        else:
            print(-1)
        continue

    time, kind, x, i = elem
    if kind:
        heappush(heap, (x, i))
    else:
        done.add(i)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    N0=2**(q-1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted(z)[::-1]:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    from random import sample
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in sample(t[:n],n):
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted(z)[::-1]:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        L,R=bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted(z)[::-1]:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[(x,bisect_left(d,s-x),bisect_left(d,t-x))for s,t,x in[map(int,t.split())for t in t[:n]]]
    z.sort(reverse=1)
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in z:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    z.sort(reverse=1)
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in z:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=sys.stdin.readlines()
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    z.sort(reverse=1)
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in z:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    z.sort(reverse=1)
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in z:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-I]+list(map(int,t[n:]))+[I]
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    z.sort(reverse=1)
    for x,l,r in z:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-I]+list(map(int,t[n:]))+[I]
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,(bisect_left(d,s-x),bisect_left(d,t-x))))
    z.sort(reverse=1)
    for x,(l,r)in z:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-I]+list(map(int,t[n:]))+[I]
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    d=tuple([-I]+list(map(int,t[n:]))+[I])
    N0=2**(q+1).bit_length()
    data=array('i',[I]*2*N0)
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    d=array('i',[-I]+list(map(int,t[n:]))+[I])
    N0=2**(q+1).bit_length()
    data=array('i',[I]*2*N0)
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    I=10**18
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-I]+list(map(int,t[n:]))+[I]
    N0=2**(q+1).bit_length()
    data=[I]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,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=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
List_S = [list(map(int,input().split())) for i in range(N)]
List_D = [int(input()) for i in range(Q)]

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

List = []
dic = {} 
for i in range(N):
    List.append([List_S[i][0] - List_S[i][2] - 0.5, List_S[i][1] - List_S[i][2] - 0.5, List_S[i][2]])
    for j in range(int(List[i][1] - List[i][0])):
        dic.setdefault(int(List[i][0] + 0.5 + j),List[i][2])

for i in range(Q):
    if List_D[i] in dic:
        print("{}".format(dic.get(List_D[i])))
    else:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
constraction = [list(map(int, input().split())) for _ in range(N)]
constraction = sorted(constraction, key=lambda x: x[2])
D = list(int(input()) for _ in range(Q))
for q in D:
    ignore = []
    for i, c in enumerate(constraction):
        s, t, x = c
        if x < t - q:
            if s - q <= x:
                print(x)
                for j in ignore[::-1]:
                    constraction.pop(j)
                break
        else:
            ignore.append(i)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

input = sys.stdin.readline

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))

    E.sort(reverse=True)

    q = []
    done = set()
    D = [(i, d) for i, d in enumerate(D)]
    D.sort(reverse=True)
    ans = [-1] * Q
    while D:
        while E and E[-1][0] <= D[-1][1]:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, (x, i))
            else:
                done.add((x, i))

        while q and q[0] in done:
            heapq.heappop(q)

        i, d = D.pop()
        if q:
            ans[i] = q[0][0]

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


def main():
    N, Q = read_int_n()
    STX = tuple(read_int_n() for _ in range(N))
    D = tuple(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()