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 heapq
inpl = lambda: list(map(int,input().split()))

N, Q = inpl()
event = []
for _ in range(N):
    s, t, x = inpl()
    event.append((s-x,1,x))
    event.append((t-x,0,x))
for _ in range(Q):
    event.append((int(input()),2,None))
event.sort()

INFTY = 10**10
xmin = INFTY
xq = []
for t, e, x in event:
    if e == 2:
        if xmin >= INFTY:
            print(-1)
        else:
            print(xmin)
    elif e == 1:
        if x < xmin:
            heapq.heappush(xq,(xmin,1))
            xmin = x
        else:
            heapq.heappush(xq,(x,1))
    else:
        if x == xmin:
            n = 0
            while n <= 0:
                x, e = heapq.heappop(xq)
                if e == 1:
                    n += 1
                else:
                    n -= 1
            xmin = x
        else:
            heapq.heappush(xq,(x,0))

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))
class SimpleSegmentTree:
    def __init__(self, value=[], N=0, Max=10**10):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [Max] * N
        for i, v in enumerate(value):
            self.value[i] = v
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if left_v <= right_v else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if left_v <= right_v else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def globalmin(self):
        return self.value[self.node[0]]

    def query(self, l=0, r=-1):
        return self.value[self.query_index(l,r)]

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.value[self.node[R-1]] <= self.value[s]:
                    s = self.node[R-1]
            if L & 1:
                if self.value[self.node[L-1]] <= self.value[s]:
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = inpl()
event = []
for i in range(N):
    s, t, x = inpl()
    event.append((s-x,1,x,i))
    event.append((t-x,0,x,i))
for _ in range(Q):
    event.append((int(input()),2,None,None))
event.sort()

INFTY = 10**10
sg = SimpleSegmentTree(N=N, Max=INFTY)
xq = []
cur = INFTY
for t, e, x, i in event:
    if e == 2:
        if cur >= INFTY:
            print(-1)
        else:
            print(cur)
        continue
    elif e == 1:
        sg.update(i, x)
    else:
        sg.update(i, INFTY)
    new = sg.globalmin()
    if new != cur:
        cur = new

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

class SimpleSegmentTree:
    def __init__(self, value=[], N=0, Max=10**10):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [Max] * N
        for i, v in enumerate(value):
            self.value[i] = v
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if left_v <= right_v else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if left_v <= right_v else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def globalmin(self):
        return self.value[self.node[0]]

    def query(self, l=0, r=-1):
        return self.value[self.query_index(l,r)]

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.value[self.node[R-1]] <= self.value[s]:
                    s = self.node[R-1]
            if L & 1:
                if self.value[self.node[L-1]] <= self.value[s]:
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = inpl()
STX = [inpl() for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
ui = defaultdict(CountUp())
Nx = 0
for s, t, x in STX:
    if ui[x] >= Nx:
        Nx += 1
    event.append((s-x,1,x))
    event.append((t-x,0,x))
event.sort()

INFTY = 10**10
sg = SimpleSegmentTree(N=Nx, Max=INFTY)
xq = []
cur = INFTY
q = 0
for t, e, x in event:
    while q < Q and D[q] < t:
        q += 1
        if cur >= INFTY:
            print(-1)
        else:
            print(cur)
    if e == 1:
        sg.update(ui[x], x)
    else:
        sg.update(ui[x], INFTY)
    new = sg.globalmin()
    if new != cur:
        cur = new
else:
    while q < Q:
        q += 1
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
inpl = lambda: list(map(int,input().split()))

N, Q = inpl()
STX = [inpl() for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
for s, t, x in STX:
    event.append((s-x,1,x))
    event.append((t-x,0,x))
event.sort()

INFTY = 10**10
xmin = INFTY
xq = []
q = 0
for t, e, x in event:
    while q < Q and t > D[q]:
        q += 1
        if xmin >= INFTY:
            print(-1)
        else:
            print(xmin)
    if e == 1:
        if x < xmin:
            heapq.heappush(xq,(xmin,1))
            xmin = x
        else:
            heapq.heappush(xq,(x,1))
    else:
        if x == xmin:
            n = 0
            while n <= 0:
                x, e = heapq.heappop(xq)
                if e == 1:
                    n += 1
                else:
                    n -= 1
            xmin = x
        else:
            heapq.heappush(xq,(x,0))
else:
    while q < Q:
        q += 1
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
inpl = lambda: list(map(int,input().split()))

N, Q = inpl()
STX = [inpl() for _ in range(N)]
D = [(int(input()), q) for q in range(Q)]
D.sort(reverse=True)
event = []
for s, t, x in STX:
    event.append((s-x,1,x))
    event.append((t-x,0,x))
event.sort()

INFTY = 10**10
xmin = INFTY
xq = []
ans = []
for t, e, x in event:
    while D and t > D[-1][0]:
        _, q = D.pop()
        ans.append((q,xmin))
    if e == 1:
        if x < xmin:
            heapq.heappush(xq,(xmin,1))
            xmin = x
        else:
            heapq.heappush(xq,(x,1))
    else:
        if x == xmin:
            n = 0
            while n <= 0:
                x, e = heapq.heappop(xq)
                if e == 1:
                    n += 1
                else:
                    n -= 1
            xmin = x
        else:
            heapq.heappush(xq,(x,0))
else:
    while D:
        _, q = D.pop()
        ans.append((q,xmin))

ans.sort()
for _, x in ans:
    if x >= INFTY:
        print(-1)
    else:
        print(x)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = inpl()
STX = [inpl() for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
ui = defaultdict(CountUp())
Nx = 0
for s, t, x in STX:
    if ui[x] >= Nx:
        Nx += 1
    event.append((s-x,1,x))
    event.append((t-x,0,x))
event.sort()

sg = SegmentTree(N=Nx+1)
T = []
X = [None]
xq = []
cur = None
for t, e, x in event:
    if e == 1:
        sg.update(ui[x], x)
    else:
        sg.update(ui[x], None)
    new = sg.query()
    if new != cur:
        T.append(t)
        X.append(new)
        cur = new

for d in D:
    x = X[bisect_right(T,d)]
    if x == None:
        print(-1)
    else:
        print(x)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
import heapq
inpl = lambda: list(map(int,input().split()))

N, Q = inpl()
STX = [inpl() for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
for s, t, x in STX:
    event.append((s-x,1,x))
    event.append((t-x,0,x))
event.sort()

INF = 10**10
T = []
X = [INF]
xq = []
for t, e, x in event:
    if e == 1:
        if x < X[-1]:
            heapq.heappush(xq,(X[-1],1))
            T.append(t)
            X.append(x)
        else:
            heapq.heappush(xq,(x,1))
    else:
        if x == X[-1]:
            n = 0
            while n <= 0:
                x, e = heapq.heappop(xq)
                if e == 1:
                    n += 1
                else:
                    n -= 1
            T.append(t)
            X.append(x)
        else:
            heapq.heappush(xq,(x,0))

for d in D:
    x = X[bisect_right(T,d)]
    if x >= INF:
        print(-1)
    else:
        print(x)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        tl.append((t,2))
    tl.sort()
    wor = set()
    wcur = 0
    cur = -1
    flg = 0
    for x in tl:
        if x[1] == 1:
            wcur += 1
            wor.add(x[2])
            if cur < 0 or x[2] < cur:
                cur = x[2]
                flg = 0
        elif x[1] == 0:
            wcur -= 1 
            wor.remove(x[2])
            if x[2] == cur:
                flg = 1
            if not wcur:
                cur = -1
                flg = 0
        else:
            if flg:
                cur = min(wor)
                flg = 0
            print(cur)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        que.append(t)
        tl.append((t,2))
    tl.sort()
    wor = dict()
    wcur = 0
    cur = -1
    flg = 0
    for x in tl:
        if x[1] == 1:
            wcur += 1
            wor[x[2]] = 1
            if cur < 0 or x[2] < cur:
                cur = x[2]
                flg = 0
        elif x[1] == 0:
            wcur -= 1 
            wor[x[2]] = 0
            if x[2] == cur:
                flg = 1
            if not wcur:
                cur = -1
                flg = 0
        else:
            if flg:
                cur = min([x for x in wor if wor[x]])
                flg = 0
            d[x[0]] = cur
    for i in que:
        print(d[i])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        que.append(t)
        tl.append((t,2))
    tl.sort()
    wor = dict()
    wcur = 0
    cur = -1
    flg = 0
    for x in tl:
        if x[1] == 1:
            wcur += 1
            wor[x[2]] = 1
            if cur < 0 or x[2] < cur:
                cur = x[2]
                flg = 0
        elif x[1] == 0:
            wcur -= 1 
            wor[x[2]] = 0
            if x[2] == cur:
                flg = 1
            if not wcur:
                cur = -1
                flg = 0
        else:
            if flg:
                cur = min([x for x in wor if wor[x]])
                flg = 0
            d[x[0]] = cur
    for i in que:
        print(d[i])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
inpl = lambda: list(map(int,input().split()))
N, Q = inpl()
STX = [inpl() for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
for s, t, x in STX:
    event.append((s-x,1,x))
    event.append((t-x,0,x))
event.sort()

INF = 10**10
T = []
X = [INF]
curX = set({INF})
minx = INF
for t, e, x in event:
    if e == 1:
        curX.add(x)
        if x < minx:
            minx = x
            T.append(t)
            X.append(x)
    else:
        curX.remove(x)
        if x == minx:
            minx = min(curX)
            T.append(t)
            X.append(minx)

for d in D:
    x = X[bisect_right(T,d)]
    if x >= INF:
        print(-1)
    else:
        print(x)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
inf = float('inf')

class SegmentTree:
    def __init__(self, N):
        tmp = 1
        while tmp < N:
            tmp <<= 1
        self.N = tmp
        self.data = [inf for _ in range(2*self.N-1)]
    
    def update(self, l, r, x):
        L = l + self.N
        R = r + self.N

        while L < R:
            if R & 1:
                R -= 1
                self.data[R] = min(self.data[R], x)
            if L & 1:
                self.data[L] = min(self.data[L], x)
                L += 1
            L >>= 1; R >>= 1
    
    def value(self, k):
        k += self.N
        res = self.data[k]
        while k != 0:
            k >>= 1
            res = min(res, self.data[k])
        return res

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC128 E

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC128 E

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

n,q = LI()
stx = [LI() for _ in range(n)]
stx.sort(key = itemgetter(2))
d = [I() for _ in range(q)]
lst = [[] for _ in range(q)]
for s,t,x in stx:
    l,r = bl(d,s-x),bl(d,t-x)
    for i in range(l,r):
        lst[i].append(x)
for i in lst:
    if len(i) == 0:
        print(-1)
    else:
        print(i[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC128 E

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC128 E

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC128 E

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

n,q = LI()
stx = [LI() for _ in range(n)]
stx.sort(key = itemgetter(2))
d = [I() for _ in range(q)]
ans = [-1]*q
for s,t,x in stx:
    l,r = bl(d,s-x),bl(d,t-x)
    #l≦d<rを満たすdがxでぶつかる
    for j in range(l,r):
        if ans[j] == -1:
            ans[j] = x
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


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

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

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

    # i+1番目からR番目まで足すとt以上となるような最小のRを返す
    def bisect_plus(self, i, t):
        L = i
        R = self.size
        R_prev = R
        sum_i = self.sum(i)
        while True:
            range_sum = self.sum(R) - sum_i
            if range_sum < t:
                if R == self.size:
                    return self.size + 1
                L, R = R, R_prev
            else:
                R_prev = R
                R = (L + R + 1) // 2
                if R == R_prev:
                    return R

    # L番目からi-1番目まで足すとt以上となるような最小のRを返す
    def bisect_minus(self, i, t):
        L = 1
        R = i
        L_prev = L
        sum_i = self.sum(i - 1)
        while True:
            range_sum = sum_i - self.sum(L - 1)
            if range_sum < t:
                if L == 1:
                    return 0
                L, R = L_prev, L
            else:
                L_prev = L
                L = (L + R) // 2
                if L == L_prev:
                    return L


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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left
import random
from itertools import permutations, accumulate, combinations
import sys
import string


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 998244353


n, q = LI()
L = LIR(n)
start_time = IR(q)
L = [(s - x, t - 1 - x, x) for s, t, x in L]
heapify(L)
x_sort_q = []
for i in start_time:
    while L and L[0][0] <= i:
        s, t, x = heappop(L)
        heappush(x_sort_q, (x, t))
    while x_sort_q and x_sort_q[0][1] < i:
        heappop(x_sort_q)
    if x_sort_q:
        print(x_sort_q[0][0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,0,x,i), (t-x,1,x,i)]
    xs.sort()
    xs+=[(mx,0,x,i+1)]
    ys = set()
    q = int(input())
    for x in xs:
        if q < x[0]:
            for _ in range(bn):
                nys = set()
                for k in ys:
                    segl[k] = min(segl[k*2+1],segl[k*2+2])
                    nys.add((k-1)//2)
                ys = nys
            mm = segl[0] if segl[0]!= mx else -1
            ys = set()
            while True:
                if q < x[0]:
                    print(mm)
                    Q-=1
                    if Q==0:
                        sys.exit()
                    q = int(input())
                    continue
                break
        segl[x[3]+b_num-1] = mx if x[1] else x[2]
        ys.add((x[3]+b_num-2)//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,0,x,i), (t-x,1,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2,0,0))
    xs.sort()
    ys = set()
    for x in xs:
        if x[1]==2:
            for _ in range(bn):
                nys = set()
                for k in ys:
                    segl[k] = min(segl[k*2+1],segl[k*2+2])
                    nys.add((k-1)//2)
                ys = nys
            print(segl[0] if segl[0]!= mx else -1)
            ys = set()
            continue
        segl[x[3]+b_num-1] = mx if x[1] else x[2]
        ys.add((x[3]+b_num-2)//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
def query():
    p = b_num-1
    q = n+b_num-2
    res=mx
    while q-p>1:
        if p&1 == 0:
            res = min(res,segl[p])
        if q&1 == 1:
            res = min(res,segl[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,segl[p])
    else:
        res = min(min(res,segl[p]),segl[q])
    return res


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

Submission status: Time Limit Exceeded

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

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
def query():
    p = b_num-1
    q = n+b_num-2
    res=mx
    while q-p>1:
        if p&1 == 0:
            res = min(res,segl[p])
        if q&1 == 1:
            res = min(res,segl[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,segl[p])
    else:
        res = min(min(res,segl[p]),segl[q])
    return res

input = sys.stdin.readline

xs = []
for i in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
for _ in range(Q):
    xs.append((int(input()),2))
xs.sort(key=lambda x:x[0])

for x in xs:
    if x[1]==2:
        c = query()
        print(c if c!= mx else -1)
        continue
    update(x[3], x[2] if x[1] else mx)