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 operator import itemgetter
import bisect


class LazySegmentTree():

    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
        self.lazy = [0] * (2*self.size - 1)
        self.is_lazy = [False] * (2*self.size - 1)

       
    def lazy_eval(self, k, l, r):
        if self.is_lazy[k]:
            self.node[k] = self.lazy[k]
            if r - l > 1:
                self.lazy[2*k+1] = self.lazy[k]
                self.lazy[2*k+2] = self.lazy[k]
                self.is_lazy[2*k+1] = True
                self.is_lazy[2*k+2] = True
            self.is_lazy[k] = False

    def update(self, begin, end, val, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return
        if begin <= l and r <= end:
            self.lazy[k] = val
            self.is_lazy[k] = True
            self.lazy_eval(k, l, r)
        else:
            self.update(begin, end, val, 2*k+1, l, (l+r)//2)
            self.update(begin, end, val, 2*k+2, (l+r)//2, r) 
            self.node[k] = self.node[2*k+1] + self.node[2*k+2] 

    def get_sum(self, begin, end, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return 0
        if begin <= l and r <= end:
            return self.node[k]
        vl = self.get_sum(begin, end, 2*k+1, l, (l+r)//2)
        vr = self.get_sum(begin, end, 2*k+2, (l+r)//2, r)
        return vl + vr


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(input()) for i in range(q)]

coord_li = []
for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    coord_li += [a, b]
list1, compressed_memo, len_memo = compress(coord_li)

#番兵を置くために+1しておく
st = LazySegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)

for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    if st.get_sum(num-1, num) == 0:
        print(-1)
    else:
        print(info[st.get_sum(num-1, num)-1][2])

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while(e[0] > d):
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
E = [None]*2*N
for n in range(N):
	a,b,c = map(int,inputs().split())
	E[2*n] = [a - c, 1, c]
	E[2*n + 1] = [b - c, -1, c]
E.sort(key=itemgetter(0))
mini = 1000000001
kouho = {1000000001}
my_add = kouho.add
my_discard = kouho.discard
q = 0
d = int(inputs())
flag = False
cont = False
for e in E:
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if e[1] == 1:
		my_add(e[2])
		if mini > e[2]:
			mini = e[2]
	elif e[1] == -1:
		my_discard(e[2])
		cont = False
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop


def main():
    N, Q = map(int, input().split())
    construction = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        construction[i] = (S-X, T-X, X)
    construction.sort(reverse=True)
    D = [int(input()) for _ in range(Q)]
    q = []
    for i in range(Q):
        while len(construction) and construction[-1][0] <= D[i]:
            sx, tx, x = construction.pop()
            heappush(q, (x, tx))
        while len(q) and q[0][1] <= D[i]:
            heappop(q)
        if len(q):
            print(q[0][0])
        else:
            print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
E = [None]*2*N
for n in range(N):
	a,b,c = map(int,inputs().split())
	E[2*n] = [a - c, 1, c]
	E[2*n + 1] = [b - c, -1, c]
#E.sort(key = lambda x:x[0])
E.sort(key=itemgetter(0))
mini = 1000000001
kouho = [1000000001]
q = 0
d = int(inputs())
flag = False
cont = False
for e in E:
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
		mini = min(e[2],mini)
	elif e[1] == -1:
		kouho.remove(e[2])
		cont = False
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
E = [None]*2*N
for n in range(N):
	a,b,c = map(int,inputs().split())
	E[2*n] = [a - c, 1, c]
	E[2*n + 1] = [b - c, -1, c]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = int(inputs())
flag = False
cont = False
for e in E:
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
		mini = min(e[2],mini)
	elif e[1] == -1:
		kouho.remove(e[2])
		cont = False
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BinTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root:
            self.root.insert(value)
        else:
            self.root = BinTreeNode(value)

    def exists(self, value):
        if self.root:
            return self.root.exists(value)
        else:
            return False

    def min(self):
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

    def remove(self, value):
        if self.root:
            self.root = self.root.remove(value)

    def sort(self):
        if self.root:
            return self.__walk(self.root)
        else:
            return []

    def __walk(self, target):
        ret = []
        if target.left:
            ret += self.__walk(target.left)
        ret += [target.value]
        if target.right:
            ret += self.__walk(target.right)
        return ret


class BinTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = BinTreeNode(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = BinTreeNode(value)

    def exists(self, value):
        if value == self.value:
            return True
        elif value < self.value:
            if self.left:
                return self.left.exists(value)
            else:
                return False
        elif value > self.value:
            if self.right:
                return self.right.exists(value)
            else:
                return False

    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self.value

    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self.value

    def __removenode(self):
        if self.left and self.right:
            value = self.left.max()
            self.value = value
            self.left = self.left.remove(value)
            return self
        elif self.left:
            return self.left
        elif self.right:
            return self.right
        else:
            return None

    def remove(self, value, par=None):
        if value == self.value:
            return self.__removenode()
        elif value < self.value:
            self.left = self.left.remove(value, self)
        elif value > self.value:
            self.right = self.right.remove(value, self)
        return self


def main():
    N, Q = map(int, input().split())
    query = [None] * (2 * N + Q)
    for i in range(N):
        S, T, X = map(int, input().split())
        query[i*2] = (S-X, 0, X)
        query[i*2+1] = (T-X-1, 2, X)
    for i in range(Q):
        D = int(input())
        query[2*N+i] = (D, 1, 0)
    query.sort(itemgetter(0, 1))
    bt = BinTree()
    for t, q, x in query:
        if q == 0:
            bt.insert(x)
        elif q == 1:
            print(bt.min() or -1)
        elif q == 2:
            bt.remove(x)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
E = [None]*2*N
for n in range(N):
	a,b,c = map(int,inputs().split())
	E[2*n] = [a - c, 1, c]
	E[2*n + 1] = [b - c, -1, c]
#D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = int(inputs())
flag = False
for e in E:
	cont = False
	mini = 1000000001
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
	elif e[1] == -1:
		kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = D[0]
flag = False
for e in E:
	cont = False
	mini = 1000000001
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = D[q]
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
	elif e[1] == -1:
		kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure.sort()

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

    ans = np.full(Q, 10**9, dtype=np.int)
    mask = np.full(Q, -1, dtype=np.int)
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        ans[left:right] = np.minimum(ans[left:right], pos)
        mask[left:right] = pos

    ans = np.minimum(ans, mask)

    return ans


if __name__ == '__main__':
    print(*main(), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure.sort()

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

    ans = [-1] * Q
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        while left < right:
            if ans[left] == -1:
                ans[left] = pos

            left += 1

    return ans


if __name__ == '__main__':
    print(*main(), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure = sorted(closure, key=lambda x: x[0])

    D = []
    index = defaultdict(lambda: 0)
    for i in range(Q):
        d = int(input())
        D.append(d)
        index[d] = i

    D.sort()

    ans = [0] * Q
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        for blocked in D[left:right]:
            ans[index[blocked]] = pos

        D = D[0:left] + D[right:]

    for blocked in D:
        ans[index[blocked]] = -1

    return ans



if __name__ == '__main__':
    print(*main(), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
class BinTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root:
            self.root.insert(value)
        else:
            self.root = BinTreeNode(value)

    def exists(self, value):
        if self.root:
            return self.root.exists(value)
        else:
            return False

    def min(self):
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

    def remove(self, value):
        if self.root:
            self.root = self.root.remove(value)

    def sort(self):
        if self.root:
            return self.__walk(self.root)
        else:
            return []

    def __walk(self, target):
        ret = []
        if target.left:
            ret += self.__walk(target.left)
        ret += [target.value]
        if target.right:
            ret += self.__walk(target.right)
        return ret


class BinTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = BinTreeNode(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = BinTreeNode(value)

    def exists(self, value):
        if value == self.value:
            return True
        elif value < self.value:
            if self.left:
                return self.left.exists(value)
            else:
                return False
        elif value > self.value:
            if self.right:
                return self.right.exists(value)
            else:
                return False

    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self.value

    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self.value

    def __removenode(self):
        if self.left and self.right:
            value = self.left.max()
            self.value = value
            self.left = self.left.remove(value)
            return self
        elif self.left:
            return self.left
        elif self.right:
            return self.right
        else:
            return None

    def remove(self, value, par=None):
        if value == self.value:
            return self.__removenode()
        elif value < self.value:
            self.left = self.left.remove(value, self)
        elif value > self.value:
            self.right = self.right.remove(value, self)
        return self


def main():
    N, Q = map(int, input().split())
    query = [None] * (2 * N + Q)
    for i in range(N):
        S, T, X = map(int, input().split())
        query[i*2] = (S-X, 0, X)
        query[i*2+1] = (T-X-1, 2, X)
    for i in range(Q):
        D = int(input())
        query[2*N+i] = (D, 1, 0)
    query.sort()
    bt = BinTree()
    for t, q, x in query:
        if q == 0:
            bt.insert(x)
        elif q == 1:
            print(bt.min() or -1)
        elif q == 2:
            bt.remove(x)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        heappush(closure, (pos, start, end))

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

    ans = []
    while len(closure) > 0:
        pos, start, end = heappop(closure)

        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        for blocked in D[left:right]:
            heappush(ans, (blocked, pos))

        D = D[0:left] + D[right:]

    for blocked in D:
        heappush(ans, (blocked, -1))

    while len(ans) > 0:
        _, pos = heappop(ans)
        print(pos)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = D[0]
flag = False
for e in E:
	cont = False
	mini = 1000000001
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			for k in kouho:
				mini = min(k,mini)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = D[q]
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
	elif e[1] == -1:
		kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure = sorted(closure, key=lambda x: x[0])

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

    D.sort()

    d = defaultdict(lambda: 0)
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        for blocked in D[left:right]:
            d[blocked] = pos

        D = D[0:left] + D[right:]

    for blocked in D:
        d[blocked] = -1

    for key in sorted(d.keys()):
        print(d[key])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
E.sort(key = lambda x:x[0])
d = int(inputs())
mini = 1000000001
kouho = [1000000001]
q = 0
flag = False
for e in E:
	while(e[0] > d):
		if kouho[0] < 1000000001:
			print(kouho[0])
		else:
			print(-1)
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		for k in range(len(kouho)):
			if e[2] < kouho[k]:
				kouho.insert(k,e[2])
				break
	elif e[1] == -1:
		kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
E.sort(key = lambda x:x[0])
d = int(inputs())
mini = 1000000001
kouho = [1000000001]
q = 0
flag = False
for e in E:
	while(e[0] > d):
		for k in kouho:
			mini = min(k,mini)
		if mini < 1000000001:
			print(mini)
			mini = 1000000001
		else:
			print(-1)
			mini = 1000000001
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
	elif e[1] == -1:
		kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

#iの値をxに更新
def update(i,x):
	i += NN - 1
	SegTree[i] = x
	while i>0:
		i = (i-1)//2
		SegTree[i] = min(SegTree[i*2+1],SegTree[i*2+2])

N,Q = inpl()
STX = [inpl() for i in range(N)]
DD = [[-int(input()),1,i,i] for i in range(Q)]

for i,[S,T,X] in enumerate(STX):
    l = X - (T-0.5)
    r = X - (S-0.5)
    DD.append([l,3,X,i])
    DD.append([r,2,X,i])

DD.sort()

NN = 1
while NN < N:
	NN *= 2
SegTree = [INF]*(NN*2-1)

ans = [0]*Q
for k,q,x,i in DD:
    if q == 1:
        ans[x] = SegTree[0]
    elif q == 3:
        update(i,x)
    else:
        update(i,INF)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = D[0]
flag = False
for e in E:
	while(e[0] > d):
		for k in kouho:
			mini = min(k,mini)
		if mini < 1000000001:
			print(mini)
			mini = 1000000001
		else:
			print(-1)
			mini = 1000000001
		if q < Q-1:
			q = q + 1
			d = D[q]
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if  e[1] == 1:
		kouho.append(e[2])
	elif e[1] == -1:
		kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    X = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        X.append((pos, start, end))

    X = sorted(X, key=lambda x: x[0])
    positions = np.zeros(N+1, dtype=np.int)
    starts = np.zeros(N+1, dtype=np.int)
    ends = np.zeros(N+1, dtype=np.int)
    for i, (pos, start, end) in enumerate(X):
        positions[i] = pos
        starts[i] = start
        ends[i] = end

    positions[N] = -1
    starts[N] = -1
    ends[N] = 10**9

    for _ in range(Q):
        d = int(input())

        before = (positions + d) >= starts
        after = (positions + d) < ends
        check = before * after

        print(positions[check][0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# [時間、変数、処理の種類]をイベントに追加。処理の種類は1：工事開始、2：工事終了、3：判定
from heapq import *
n, q = map(int, input().split())
events = []
ans = [-1] * q
koji = []
for _ in range(n):
    s, t, x = map(int, input().split())
    events += [[s - x - 0.3, x, 1]]
    events += [[t - x - 0.7, x, 2]]
for i in range(q):
    d = int(input())
    events += [[d, i, 3]]
events.sort()
for j, h, s in events:
    if s == 1:
        heappush(koji,h)
    elif s == 2:
        koji.remove(h)
        heapify(koji)
    else:
        if koji:
            ans[h] = koji[0]
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:


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

intervals = []

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

ds = []
for i in range(q):
    d = int(input())
    ds.append(d)


# print(intervals)
# print(ds)

# intervals = [[-3, 3, 10], [-1, 1, 2], [1, 2, 2], [5, 7, 13]]
# ds = [0, 1, 2, 3, 5, 8]


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

for d in ds:
    for i in intervals:
        if d >= i[0] and d < i[1]:
            print(i[2])
            break
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]

mini = 1000000001
count = 0
for q in [None]*Q:
	m = int(inputs())
	num = mini
	for v in V:
		if v[0]-v[2]<=m and m <= v[1]-v[2]-1:
			num = min(v[2],num)
	if num == mini:
		print(-1)
	else:
		print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
 
N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [10**15] * (2 << (n + 1).bit_length())
 
    def update(self, l, r, val) :
      l += len(self.A) // 2
      r += len(self.A) // 2
      while l < r:
          if l & 1 :
              self.A[l] = min(self.A[l], val)
              l += 1
          if r & 1:
              self.A[r-1] = min(self.A[r-1], val)
              r -= 1
          l //= 2
          r //= 2

    def get(self, i) :
      i += len(self.A) // 2
      ret = self.A[i]
      while i > 0 :
          i //= 2
          ret = min(ret, self.A[i])
      return ret if ret < 10**15 else -1

ST = SegTree(Q)
for g in G :
    s = g[0] - g[2]
    e = g[1] - g[2]
 
    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)
 
    if ll == rr :
        continue
 
    ST.update(ll, rr, g[2])
 
for i in range(Q) :
    ans = ST.get(i)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
 
N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]
 
G.sort(key = lambda x : -x[2])

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [None] * (2 << (n + 1).bit_length())
 
    def update(self, i, l, r, ll, rr, val) :
        if r <= ll or rr <= l :
            return
        if ll <= l and r <= rr :
            self.A[i] = val
            return
 
        if self.A[i] != None :
            self.A[i * 2] = self.A[i * 2 + 1] = self.A[i]
            self.A[i] = None
 
        m = (l + r) // 2
        self.update(i * 2, l, m, ll, rr, val)
        self.update(i * 2 + 1, m, r, ll, rr, val)
 
    def get(self, i, l, r, p) :
        while True :
            if self.A[i] != None or l + 1 == r :
                return self.A[i]
            m = (l+r) // 2
            if p < m :
                i = i * 2
                r = m
            else :
                i = i * 2 + 1
                l = m
 
ST = SegTree(Q)
for g in G :
    s = max(0, g[0] - g[2])
    e = g[1] - g[2]
    if e <= 0 :
        continue
 
    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)
 
    if ll == rr :
        continue
 
    ST.update(1, 0, Q, ll, rr, g[2])
 
for i in range(Q) :
    ans = ST.get(1, 0, Q, i)
    if ans == None :
        print(-1)
    else :
        print(ans)