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:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 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 input()

def main():
    N, Q = LI()
    events = []
    for _ in range(N):
        s, t, x = LI()
        s -= x + 0.5
        t -= x + 0.5
        events.append([s, x])
        events.append([t, -x])
    for _ in range(Q):
        d = II()
        events.append([d, 0])
    events.sort()
    dst = {INF}
    for t, x in events:
        if x == 0: # query
            y = min(dst)
            if y == INF:
                y = -1
            print(y)
        elif x > 0: # add
            dst.add(x)
        else: # x < 0, delete
            dst.remove(-x)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

def readInt():
    return int(input())

def readList():
    return list(input().split())

def readListI():
    return list(map(int, input().split()))

# index が条件を満たすかどうか
def isOK(l, index, key):
    if (l[index][0] >= key): return True
    else: return False

def binary_search(l, key, ret_right=True):
    left = -1 #「index = 0」が条件を満たすこともあるので、初期値は -1
    right = len(l) # 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    while (right - left > 1):
        mid = (int)(left + (right - left) / 2)

        if (isOK(l, mid, key)): right = mid
        else: left = mid

    # left は条件を満たさない最大の値、right は条件を満たす最小の値になっている
    if ret_right:
        return right
    else:
        return left

def main():
    ld = []
    n, q = readListI()
    ll = []
    for _ in range(n):
        s, t, x = readListI()
        ll.append((x, s, t))
    ll.sort()
    for i in range(q):
        ld.append((readInt(), i))
    ret = [-1 for _ in range(q)]
    for i in range(n):
        s = ll[i][1]-ll[i][0]-0.5
        t = ll[i][2]-ll[i][0]-0.5
        l = binary_search(ld, s)
        r = binary_search(ld, t, ret_right=False)
        if r >= 0 and l < len(ld):
            for d in ld[l:r+1]:
                ret[d[1]] = ll[i][0]
            ld = ld[:l] + ld[r+1:]
    for e in ret:
        print(e)


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

n = N

for i in range(Q):
    flag = 0
    count = 0
    for j in range(n):
        if List_S[j-count][1] - 0.5 < (List_D[i] + List_S[j-count][2]):
            del List_S[j-count]
            count += 1
        elif (List_S[j-count][0] - 0.5 < (List_D[i] + List_S[j-count][2])) and ((List_D[i] + List_S[j-count][2]) < List_S[j-count][1]-0.5):
            print("{}".format(List_S[j-count][2]))
            flag = 1
            break
    n = n - count
    if flag == 0:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:

N,Q = map(int,input().split())
INF = 10**10
evt = []
for i in range(N):
	s,t,x = map(int,input().split())
	if t-x < 0:
		continue
	evt.append((s-x,1,x))
	evt.append((t-x,-1,x))
ans = [0 for i in range(Q)]
for i in range(Q):
	evt.append((int(input()), 10, i))
evt.sort()

cnt = 0
s = set([INF])
for e in evt:
	if e[1] == 1:
		s.add(e[2])
	elif e[1] == -1:
		s.remove(e[2])
	elif e[1] == 10:
		ans[e[2]] = min(s)

for a in ans:
	print(a if a != INF else -1)

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

n = N

for i in range(Q):
    flag = 0
    count = 0
    for j in range(n):
        if List_S[j-count][1] - 0.5 < List_D[i]:
            del List_S[j-count]
            count += 1
        elif (List_S[j-count][0] - 0.5 < (List_D[i] + List_S[j-count][2])) and ((List_D[i] + List_S[j-count][2]) < List_S[j-count][1]-0.5):
            print("{}".format(List_S[j-count][2]))
            flag = 1
            break
    n = n - count
    if flag == 0:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heapify

N, Q = map(int, input().split())
INF = 10 ** 9
event, pos, D = [], [], []
for _ in range(N):
    s, t, x = map(int, input().split())
    # append event
    event.append((s-x-0.5, 1, x))
    # delete event
    event.append((t-x-0.5, -1, x))

for _ in range(Q):
    event.append((int(input()), 0, 0))

event.sort()

for ev in event:
    # work event
    time, type, x = ev
    if type == 1:
        # pos.append(x)
        heappush(pos, x)
    elif type == -1:
        pos.remove(x)
        heapify(pos)
    else:
        if len(pos) == 0:
            print(-1)
        else:
            print(pos[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import collections
import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    N, Q = read_int_array()
    add, delete = [], []
    for i in range(N):
        S, T, X = read_int_array()
        add.append((S - X, X))
        delete.append((T - X, X))

    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(add)
    heapq.heapify(delete)
    for _ in range(Q):
        x = read_int()
        while add and add[0][0] <= x:
            coord, val = heapq.heappop(add)
            heapq.heappush(active, val)

        while delete and delete[0][0] <= x:
            coord, val = heapq.heappop(delete)
            to_delete[val] += 1

        while active and to_delete[active[0]] > 0:
            to_delete[active[0]] -= 1
            heapq.heappop(active)

        print(active[0] if active else -1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion


def read():
    return input()


def read_array(sep=None, maxsplit=-1):
    return read().split(sep, maxsplit)


def read_int():
    return int(read())


def read_int_array(sep=None, maxsplit=-1):
    return [int(a) for a in read_array(sep, maxsplit)]


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
event={}
for i in range(n):
     s,t,x=map(int,input().split())
     s-=x
     t-=x
     try:
          event[s].append([1,x])
     except:
          event[s]=[[1,x]]
     try:
          event[t].append([0,x])
     except:
          event[t]=[[0,x]]
d=[]
for i in range(q):
     d.append(int(input()))
s=set()
k=sorted(event.keys())
i=0
f=True
k_=k[i]
for a in d:
     while(k_<=a and f):
          for x in event[k_]:
               if x[0]==1:
                    s.add(x[1])
               else:
                    s.remove(x[1])
          i+=1
          try:
               k_=k[i]
          except:
               f=False
               break
     try:
          print(min(s))
     except:
          print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
from __pypy__ import builders
readline = sys.stdin.readline
N, Q = map(int, readline().split())
U = [0]*N
qs = []
for i in range(N):
    s, t, x = map(int, readline().split())
    qs.append((s-x, x, i, 1))
    qs.append((t-x, x, i, 0))
qs.sort()

b = builders.StringBuilder(Q)
que = []
j = 0
for i in range(Q):
    d = int(readline())
    while j < 2*N and qs[j][0] <= d:
        _, x, i, m = qs[j]
        if m:
            heappush(que, (x, i))
        else:
            U[i] = 1
        j += 1
    while que and U[que[0][1]]:
        heappop(que)
    if que:
        b.append("%d\n" % que[0][0])
    else:
        b.append("-1\n")
sys.stdout.write(b.build())

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]
# イベントを入れる配列 [時間, 追加or削除のフラグ, 場所, 人のフラグ]
event=[]
for s,t,x in stx:
    event.append([s-x,True,x,False])
    event.append([t-x,False,x,False])
for i in range(q):
    event.append([d[i],False,i,True])

event.sort(key=lambda x:x[0])
# print(event)
stop=[-1 for _ in range(q)]
place=[]
for t, isHappen, x, isHuman in event:
    if isHuman:
        if len(place)>0:
            stop[x]=min(place)
    else:
        if isHappen:
            place.append(x)
        else:
            place.remove(x)
# print(stop)
for s in stop:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
from __pypy__ import builders
readline = sys.stdin.readline
N, Q = map(int, readline().split())
U = [0]*N
qs = []
for i in range(N):
    s, t, x = map(int, input().split())
    qs.append((s-x, x, i, 1))
    qs.append((t-x, x, i, 0))
qs.sort()

b = builders.StringBuilder(Q)
que = []
j = 0
for i in range(Q):
    d = int(input())
    while j < 2*N and qs[j][0] <= d:
        _, x, i, m = qs[j]
        if m:
            heappush(que, (x, i))
        else:
            U[i] = 1
        j += 1
    while que and U[que[0][1]]:
        heappop(que)
    if que:
        b.append("%d\n" % que[0][0])
    else:
        b.append("-1\n")
sys.stdout.write(b.build())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heapify

N, Q = map(int, input().split())
INF = 10 ** 9
event, pos, D = [], [], []
for _ in range(N):
    s, t, x = map(int, input().split())
    # append event
    event.append((s-x-0.5, 1, x))
    # delete event
    event.append((t-x-0.5, -1, x))

for _ in range(Q):
    event.append((int(input()), 0, 0))

event.sort()

for ev in event:
    # work event
    time, type, x = ev
    if type == 1:
        pos.append(x)
    elif type == -1:
        pos.remove(x)
    else:
        if len(pos) == 0:
            print(-1)
        else:
            print(min(pos))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 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 input()
from bisect import bisect

def main():
    N, Q = LI()
    XST = []
    ts = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
        ts.append(s)
        ts.append(t)
    ts.sort()
    ts.append(INF)
    D = []
    for _ in range(Q):
        D.append(II())
    xs = [INF] * (N * 2 + 1)
    XST.sort(reverse=True)
    for x, s, t in XST:
        s0 = bisect(ts, s)
        t0 = bisect(ts, t)
        for i in range(s0, t0):
            xs[i] = x
    for d in D:
        y = bisect(ts, d)
        y = xs[y]
        if y == INF:
            y = -1
        print(y)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]
# イベントを入れる配列 [時間, 追加or削除のフラグ, 場所]
event=[]
for s,t,x in stx:
    event.append([s-x,True,x])
    event.append([t-x,False,x])
event.sort(key=lambda x:x[0])
# print(event)
stop=[-1 for _ in range(q)]
for i in range(q):
    place=[]
    for t, isHappen, x in event:
        if t>d[i]:
            break
        if isHappen:
            place.append(x)
        else:
            place.remove(x)
    if len(place)>0:
        stop[i]=min(place)
# print(stop)
for s in stop:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
from __pypy__ import builders
readline = sys.stdin.readline
N, Q = map(int, readline().split())

data = [0]*(N+2)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N+1 and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

P = [list(map(int, readline().split())) for i in range(N)]
*S, = set(x for s, t, x in P)
S.sort()
mp = {e: i for i, e in enumerate(S)}
D = [int(readline()) for i in range(Q)]
que = []
for s, t, x in P:
    y = mp[x]
    que.append((s-x, y, 1))
    que.append((t-x, y, -1))
que.sort()
b = builders.StringBuilder(Q)
i = 0
for d in D:
    while i < 2*N and que[i][0] <= d:
        _, j, f = que[i]
        add(j+1, f)
        i += 1
    k = lower_bound(0)
    if k == N+2:
        b.append("-1\n")
    else:
        b.append("%d\n" % S[k-1])
sys.stdout.write(b.build())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import collections
import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    N, Q = [int(x) for x in input().split()]
    updates = []
    for i in range(N):
        S, T, X = [int(x) for x in input().split()]
        updates.append((S - X, 1, X))
        updates.append((T - X, -1, X))

    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(updates)
    for _ in range(Q):
        x = int(input())
        while updates and updates[0][0] <= x:
            coord, tp, val = heapq.heappop(updates)

            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)

            while active and to_delete[active[0]] > 0:
                to_delete[active[0]] -= 1
                heapq.heappop(active)
        print(active[0] if active else -1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

X = sorted(X, key = lambda x: x[0])
i = 0
A, B, C = [], [], []
for _ in range(Q):
    d = int(input())
    while i < len(X) and d >= X[i][0]:
        a, b, x = X[i]
        heappush(A, (x, b))
        heappush(B, (b, x))
        i += 1
    while len(B) and B[0][0] <= d:
        b, x = heappop(B)
        heappush(C, (x, b))
    while len(C) and len(A) and C[0][0] == A[0][0]:
        heappop(A)
        heappop(C)
    print(A[0][0] if A else -1)

Submission status: Time Limit Exceeded

Solution code:
n,Q = [int(i) for i in input().split()]
from heapq import  *

stx=[]
for j in range(n):
    a = [int(i) for i in input().split()]
    stx.append([a[0]-a[2],a[1]-a[2],a[2]])
q = [int(input()) for i in range(Q)]
stx.sort()

xt=[]
pt=0
for d in q:
    while pt < n and stx[pt][0] <= d:
        heappush(xt,(stx[pt][2],stx[pt][1]))
        pt+=1
    while xt and xt[0][1] <= d:
        heappop(xt)
    if xt:
        print(xt[0][0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import collections
import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    N, Q = read_int_array()
    updates = []
    for i in range(N):
        S, T, X = read_int_array()
        updates.append((S - X, 1, X))
        updates.append((T - X, -1, X))

    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(updates)
    for _ in range(Q):
        x = read_int()
        while updates and updates[0][0] <= x:
            coord, tp, val = heapq.heappop(updates)

            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)

            while active and to_delete[active[0]] > 0:
                to_delete[active[0]] -= 1
                heapq.heappop(active)
        print(active[0] if active else -1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion


def read():
    return input()


def read_array(sep=None, maxsplit=-1):
    return read().split(sep, maxsplit)


def read_int():
    return int(read())


def read_int_array(sep=None, maxsplit=-1):
    return [int(a) for a in read_array(sep, maxsplit)]


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 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 input()
from bisect import bisect

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ts = []
    for x, s, t in XST:
        ts.append(s)
        ts.append(t)
    ts.sort()
    ts.append(INF)
    xs = [INF] * (N * 2 + 1)
    XST.sort(reverse=True)
    for x, s, t in XST:
        s0 = bisect(ts, s)
        t0 = bisect(ts, t)
        for i in range(s0, t0):
            xs[i] = x
    for d in D:
        y = bisect(ts, d)
        y = xs[y]
        if y == INF:
            y = -1
        print(y)
    return

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[1], reverse=True)
MAX_T = List_S[0][1]
List_S.sort(key=lambda x:x[0])
List_S.sort(key=lambda x:x[2])

for i in range(Q):
    flag = 0
    if List_D[i] > MAX_T:
        print("-1")        
    else:
        for j in range(N):
            if (List_S[j][0]-0.5 < (List_D[i] + List_S[j][2])) and ((List_D[i] + List_S[j][2]) < List_S[j][1]-0.5):
                print("{}".format(List_S[j][2]))
                flag = 1
                break
    if flag == 0:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

events = []
for _ in range(n):
	s,t,x = map(int, input().split())
	e1 = (max(0,s-x), 1, x)
	e2 = (max(0,t-x), -1, x)
	events.append(e1)
	events.append(e2)

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

dep_time = [int(input()) for _ in range(q)]

working = []
current_ev_i = 0
flg = False
for dep_t in dep_time:
	if not flg and events[current_ev_i][0] <= dep_t:
		while events[current_ev_i][0] <= dep_t:
			event = events[current_ev_i]
			if event[1] == 1:
				working.append(event[2])
			elif event[1] == -1:
				working.remove(event[2])
			current_ev_i = current_ev_i + 1
			if current_ev_i >= len(events):
				flg = True
				break

	if working:
		print(min(working))
	else:
		print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import collections
import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


class Node:

    def __init__(self, start, end):
        self.start, self.end, self.mid = start, end, (start + end) // 2
        self.val = float('inf')
        self.left = self.right = None


class NumArray:

    def __init__(self, x):
        x.sort()
        self.x_i = {v: i for i, v in enumerate(x)}

        def createTree(l, r):
            if l >= r:
                return None
            root = Node(l, r)
            if l + 1 == r:
                return root
            mid = root.mid
            root.left = createTree(l, mid)
            root.right = createTree(mid, r)
            return root

        self.root = createTree(0, len(x) - 1)

    def update(self, x1, x2, val):
        def updateVal(root, i, j):
            if root.start == i and root.end == j:
                root.val = min(root.val, val)
            else:
                mid = root.mid
                if i < mid:
                    updateVal(root.left, i, min(mid, j))
                if mid < j:
                    updateVal(root.right, max(mid, i), j)

        return updateVal(self.root, self.x_i[x1], self.x_i[x2])

    def query(self, x):
        def queryVal(root, i):
            if not root or i < root.start or i >= root.end:
                return float('inf')
            else:
                return min(root.val, queryVal(root.left, i), queryVal(root.right, i))

        return queryVal(self.root, self.x_i[x])


def main():
    N, Q = read_int_array()
    updates = []
    for i in range(N):
        S, T, X = read_int_array()
        updates.append((S - X, 1, X))
        updates.append((T - X, -1, X))

    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(updates)
    for _ in range(Q):
        x = read_int()
        while updates and updates[0][0] <= x:
            coord, tp, val = heapq.heappop(updates)

            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)

            while active and to_delete[active[0]] > 0:
                to_delete[active[0]] -= 1
                heapq.heappop(active)
        print(active[0] if active else -1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion


def read():
    return input()


def read_array(sep=None, maxsplit=-1):
    return read().split(sep, maxsplit)


def read_int():
    return int(read())


def read_int_array(sep=None, maxsplit=-1):
    return [int(a) for a in read_array(sep, maxsplit)]


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
N, Q = map(int, readline().split())

data = [0]*(N+2)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k > 0:
        s += data[k]
        k -= k & -k
    return s
N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N+1 and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

P = [list(map(int, readline().split())) for i in range(N)]
S = sorted(set(x for s, t, x in P))
mp = {e: i for i, e in enumerate(S)}
D = [int(readline()) for i in range(Q)]
que = []
for s, t, x in P:
    y = mp[x]
    que.append((s-x, y, 1))
    que.append((t-x, y, -1))
que.sort()
ans = []
i = 0
for d in D:
    while i < 2*N and que[i][0] <= d:
        _, j, f = que[i]
        add(j+1, f)
        i += 1
    k = lower_bound(0)
    if k == N+2:
        ans.append("-1\n")
    else:
        ans.append("%d\n" % S[k-1])
sys.stdout.writelines(ans)