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: Wrong Answer

Solution code:
import heapq
n, q = map(int, raw_input().split(" "))

events = []

for i in range(0, n):
    s, t, x = map(int, raw_input().split(" "))
    events.append(((s - x) * 10 + 0, 1, i, x))
    events.append(((t - x) * 10 + 1, 2, i, x))

for i in range(0, q):
    d = int(raw_input())
    events.append(((d * 10) + 2, 0, i, 0))

sort = sorted(events, key=lambda (a, b, c, d): a)
# print(sort)

ans = [-10 for i in range(0, q)]
const = set()
min_pos = -1
pos_index = [-1 for i in range(0, n)]
for i in range(0, len(sort)):
    key, state, index, pos = sort[i]
    if state == 1:
        const.add((pos, index))
        pos_index[index] = pos
        if min_pos < 0 or min_pos > pos:
            min_pos = pos
    elif state == 2:
        #print("remove: %d" % pos_index[index])
        const.remove((pos_index[index], index))
        if min_pos == pos_index[index]:
            min_pos = -1
    else:
        if len(const) <= 0:
            ans[index] = -1
        else:
            if min_pos < 0:
                min_pos = min(const)[0]
                ans[index] = min(const)[0]
            else:
                ans[index] = min_pos
    #print(const)

for i in range(0, q):
    print(ans[i])

Submission status: Wrong Answer

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

from bisect import *

result = {}

STX = sorted(STX, key=lambda x:x[2])
ds = D[:]

for s, t, x in STX:
    t1 = s - .5 - x
    t2 = t - .5 - x
    p1 = bisect_left(ds, t1)
    p2 = bisect_left(ds, t2)
    #print(p1, p2, t1, t2, ds[p1:p2])
    for d in ds[p1:p2]:
        result[d] = x
    ds = ds[:p1] + ds[p2:]

#print(result)

for d in D:
    print(d, result.get(d, -1))

Submission status: Wrong Answer

Solution code:
import collections

N, Q = map(int, input().split())
maxX = 10 ** 9 + 1
stoppedDict = collections.defaultdict(set)
for i in range(N):
    s, t, x = map(int, input().split())
    stoppedDict[s-x].add(x)
    stoppedDict[t-x-1].add(x)
#print(stoppedDict)


def solve(d):
    if len(stoppedDict[d]) != 0:
        return min(stoppedDict[d])
    else:
        l = d - 1
        r = d + 1
        maxR = max(list(stoppedDict.keys()))
        if maxR < r:
            return -1
        while len(stoppedDict[l]) == 0 and l >= 2:
            l += 1
        while len(stoppedDict[r]) == 0 and maxR > r:
            r += 1
        if stoppedDict[l] == stoppedDict[r]:
            return stoppedDict[l]
        else:
            return -1


for i in range(Q):
    d = int(input())
    print(solve(d))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from operator import itemgetter
 
N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
sorted_querys = sorted(querys)
time = {}
for q in querys:
    time[q] = -1
b_left = bisect_left
check_points = sorted(check_points, key=itemgetter(2))
now = 0
for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(sorted_querys[now:], start)
    right = b_left(sorted_querys[now:], end)
    for q in sorted_querys[now:][left:right]:
        if time[q] == -1:
            time[q] = x
    now = right
for q in querys:
    print(time[q])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from operator import itemgetter
 
N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1
b_left = bisect_left
check_points = sorted(check_points, key=itemgetter(2))
now = 0
for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys[now:], start)
    right = b_left(querys[now:], end)
    for q in querys[now:][left:right]:
        if time[q] == -1:
            time[q] = x
    now = right-1
for q in querys:
    print(time[q])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from operator import itemgetter
 
N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1
b_left = bisect_left
check_points = sorted(check_points, key=itemgetter(2))
now = 0
for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys[now:], start)
    right = b_left(querys[now:], end)
    for q in querys[now:][left:right]:
        if time[q] == -1:
            time[q] = x
    now = right
for q in querys:
    print(time[q])

Submission status: Wrong Answer

Solution code:
import bisect

N, Q = map(int, input().split())

event = []
for _ in range(N) :
    s, t, x = map(int, input().split())
    event.append([s - x, True, x])
    event.append([t - x, False, x])

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

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

dk = 0
dv = D[0]

for e in event :
    if dv < e[0] :
        if len(constraction) == 0 :
            print(-1)
        else :
            print(min(constraction))

        if dk < Q - 1 :
            dk += 1
            dv = D[dk]
        else :
            break

    if e[1] :
        bisect.insort_left(constraction, e[2])
    else :
        constraction.pop(bisect.bisect_left(constraction, e[2]))

Submission status: Wrong Answer

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
			q = q + 1
			if q >= Q-1:
				flag = True
				break
			d = int(inputs())
		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: Wrong Answer

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())
	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
			q = q + 1
			if q >= Q-1:
				break
			d = int(inputs())
		else:
			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
			continue
		break
		
	for t in [None]*(Q-q):
		print(-1)
main()

Submission status: Wrong Answer

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])
print(1)

Submission status: Wrong Answer

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)
    print("WA")
 
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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())
    event = [None] * (2 * N)
    for i in range(N):
        S, T, X = map(int, input().split())
        event[i*2] = (S-X, 0, X)
        event[i*2+1] = (T-X, 1, X)
    D = [int(input()) for _ in range(Q)]
    event.sort()
    i = 0
    bt = BinTree()
    for t, q, x in event:
        if q == 0:
            bt.insert(x)
        elif q == 1:
            bt.remove(x)
        while i < Q and D[i] <= t:
            print(bt.min() or -1)
            i += 1
    while i < Q:
        print(bt.min() or -1)
        i += 1


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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)
    mask = np.full(Q, -1)
    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: Wrong Answer

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
	while(e[0] > d):
		if mini == 1000000001 and cont ==False:
			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
	cont = False
	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])
		if mini == e[2]:
			mini = 1000000001
for t in [None]*(Q-q):
	print(-1)

Submission status: Wrong Answer

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
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
				mini = 1000000001
			else:
				print(-1)
				mini = 1000000001
		else:
			for k in kouho:
				mini = min(k,mini)
			if mini < 1000000001:
				print(mini)
				mini = 1000000001
			else:
				print(-1)
				mini = 1000000001
		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: Wrong Answer

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
			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: Wrong Answer

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: Wrong Answer

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] = -2
    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: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1)
main()

Submission status: Wrong Answer

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] -1
	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
			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: Wrong Answer

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]
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:
			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: Wrong Answer

Solution code:
n,q=map(int,input().split())
stop=[]
for i in range(n):
  a=list(map(int,input().split()))
  stop.append(a)
for i in range(n):
  flag=0
  b=int(input())
  if stop[i][0]<=stop[i][2]+b<stop[i][1]:
    print(stop[i][2])
    flag=1
    break
  if flag==0:
    print(-1)

Submission status: Wrong Answer

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
for e in E:
	d = D[q]
	if 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
		else:
			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: Wrong Answer

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
for e in E:
	d = D[q]
	print(kouho)
	if e[0] > d:
		for k in kouho:
			mini = min(k,mini)
		if mini < 1000000001:
			mini = 1000000001
		else:
			print(-1)
			mini = 1000000001
		if q < Q-1:
			q = q + 1
		else:
			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: Wrong Answer

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: Wrong Answer

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 l < ll and rr < r :
            m = (l + r) // 2
            if ll < m :
                self.update(i * 2, l, m, ll, rr, val)
            if m < rr :
                self.update(i * 2 + 1, m, r, ll, rr, val)
            return
            
        if r <= ll or rr <= l :
            return

        while True :
            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
            if rr <= m :
                i = i * 2
                r = m
            elif rr < r :
                i = i * 2 + 1
                l = m
                self.A[i * 2] = val
            elif ll < m :
                i = i * 2
                r = m
                self.A[i * 2 + 1] = val
            else :
                i = i * 2 + 1
                l = m
 
    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)

Submission status: Wrong Answer

Solution code:
import sys

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])
T.sort()

A = [0] * (4 * Q + 5)

def update(A, i, l, r, ll, rr, val) :
    if r <= ll or rr <= l :
        return
    if ll <= l and r <= rr :
        A[i] = val
        return

    if A[i] != 0 :
        A[i * 2] = A[i * 2 + 1] = A[i]
        A[i] = 0

    m = (l + r) // 2
    update(A, i * 2, l, m, ll, rr, val)
    update(A, i * 2 + 1, m, r, ll, rr, val)

def get(A, i, l, r, p) :
    if A[i] != 0 or l + 1 == r :
        return A[i]
    m = (l+r) // 2
    if p < m :
        return get(A, i * 2, l, m, p)
    else :
        return get(A, i * 2 + 1, m, r, p)

def lower_bound(T, k) :
    l = 0
    r = len(T)
    while l + 1 < r :
        m = (l+r) // 2
        if T[m] < k :
            l = m
        else :
            r = m
    return r

for g in G :
    s = max(0, g[0] - g[2])
    e = g[1] - g[2]
    if e <= 0 :
        continue

    ll = lower_bound(T, s)
    rr = lower_bound(T, e)

    if ll == rr :
        continue

    update(A, 1, 0, Q, ll, rr, g[2])

for i in range(Q) :
    ans = get(A, 1, 0, Q, i)
    if ans == 0 :
        print(-1)
    else :
        print(ans)