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:
from heapq import heappush, heapify

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

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

ev.sort()

tm = -INF
iev = 0
for d in D:
    # work event
    while iev < N*2:
        nt, ni, nx = ev[iev]
        if nt > d:
            break
        if ni == 1:
            # heappush(pos, nx)
            pos.append(nx)
        else:
            pos.remove(nx)
            # heapify(pos)

        tm = nt
        iev += 1
    if len(pos) == 0:
        print(-1)
    else:
        print(0)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from bisect import bisect,bisect_left
N,Q=map(int,input().split())
table=[]
for i in range(N):
    s,t,x=map(int,input().split())
    #print((max(0,s-x),t-1-x))
    table.append((x,max(0,s-x),t-x))
H=[]
D=[int(input()) for i in range(Q)]
#print(D)
for x,a,b in table:
    #print(x,a,b,(x,bisect_left(D,a),bisect(D,b)))
    heappush(H,(bisect_left(D,a),bisect_left(D,b),x))
#print(H)
K=[]
U=[10**12]*Q
J=[]
for i in range(Q):
    while len(J)>0 and J[0][2]<=i:
        y,u,v=heappop(J)
    while len(H)>0 and H[0][0]<=i:
        a,b,x=heappop(H)
        heappush(J,(x,a,b))
    if len(J)>0:
        U[i]=J[0][0]
    #print(i,J,H,U[i])
for i in range(Q):
    if U[i]==10**12:
        print(-1)
    else:
        print(U[i])

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    def bsearch_l(val, D):
        l = -1
        r = Q - 1
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val > D[m]:
                l = m
            else:
                r = m
        #print(val, l, r)
        return r
    def bsearch_r(val, D):
        l = 0
        r = Q
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val < D[m]:
                r = m
            else:
                l = m
        #print(val, l, r)
        return l
    a = []
    for i in range(N):
        if X[i] - T[i] > 0:
            continue
        a.append([X[i], max(0, -(X[i] - S[i])), max(0, -(X[i] - T[i]) - 1)])
    a.sort(key=lambda x: x[0])
    ret = [-1] * Q
    for tmp in a:
        l = bsearch_l(tmp[1], D)
        r = bsearch_r(tmp[2], D)
        #print(tmp)
        #print(l, r)
        for i in range(l, r + 1):
            if i >= 0 and i < Q and ret[i] < 0:
                ret[i] = tmp[0]

    for r in ret:
        print(r)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]" 
    T = [int()] * (N)  # type: "List[int]" 
    X = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(N, Q, S, T, X, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
 
n,q = map(int,input().split())
x = []
for i in range(n):
        x.append(list(map(int,input().split())))
x.sort(key = lambda x : x[2])
dd = []
zaa = []
for i in range(q):
        a = int(input())
        dd.append(a)
        zaa.append(a)
y = []
 
for i in range(n):
        a = x[i][0]-x[i][2]
        b = x[i][1]-1-x[i][2]
        y.append([a,b])
        zaa.append(a)
        zaa.append(b)
import bisect
ans = [-1]*q
tobi = [-1]*q
#print(dd,y)
for i in range(n):
        xx = bisect.bisect_left(dd,y[i][0])
        yy = bisect.bisect_left(dd,y[i][1]+1)
        j = xx
 #       print(xx,yy)
 #       print(ans,tobi)
        while j < yy:
                if ans[j] == -1:
                        ans[j] = x[i][2]
                        tobi[j] = yy
                        j += 1
                        
                else:
                        tobi[j] = yy
                        j = tobi[j]
for i in ans:
        print(i)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    def bsearch_l(val, D):
        l = -1
        r = Q - 1
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val > D[m]:
                l = m
            else:
                r = m
        #print(val, l, r)
        return r
    def bsearch_r(val, D):
        l = 0
        r = Q
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val < D[m]:
                r = m
            else:
                l = m
        #print(val, l, r)
        return l
    a = []
    for i in range(N):
        if X[i] - T[i] >= 0:
            continue
        a.append([X[i], max(0, -(X[i] - S[i])), max(0, -(X[i] - T[i]) - 1)])
    a.sort(key=lambda x: x[0])
    ret = [-1] * Q
    for tmp in a:
        l = bsearch_l(tmp[1], D)
        r = bsearch_r(tmp[2], D)
        #print(tmp)
        #print(l, r)
        for i in range(l, r + 1):
            if i >= 0 and i < Q and ret[i] < 0:
                ret[i] = tmp[0]

    for r in ret:
        print(r)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]" 
    T = [int()] * (N)  # type: "List[int]" 
    X = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(N, Q, S, T, X, D)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

L = [(max(-0.5,s-x),max(-0.5,t-x),x) for s,t,x in STX] + [(d,-1) for d in D]
L.sort()

import heapq
hp = [] # (x,t-x)を入れる

for l in L:
  if l[1] == -1:
    while hp and l[0] > hp[0][1]:
      heapq.heappop(hp)
    if hp:
      print(hp[0][0])
    else:
      print(-1)
  else:
    heapq.heappush(hp, (l[2],l[1]))

Submission status: Wrong Answer

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

s = set([INF])
q_head = q.pop()
cnt = 0
for e in evt:
	if -q_head[0] < e[0]:
		ans[q_head[1]] = min(s)
		cnt += 1
		if cnt < Q:
			q_head = q.pop()
		else:
			q_head = None
			break
	if e[1] == 1:
		s.add(e[2])
	elif e[1] == -1:
		s.remove(e[2])

if q_head != None:
	ans[q_head[1]] = min(s)
for a in ans:
	print(a if a != INF else -1)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) # xで死ぬ
  heappush(q,(t-x,0,x)) # xで死ななくなる
  
D = [int(input()) for _ in range(Q)]
for i,d in enumerate(D):
  heappush(q,(d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

while q:
  a,c,b = heappop(q)
  if c == 2: # queryに答える
    if se:
      pass
      #answer[b] = min(se)
  elif c == 1:
    se.add(b)
  elif c == 0:
    se.remove(b)

    
for x in answer:
  print(x)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
INF = 10**10
evt = [(INF,1,INF+1)]
for i in range(N):
	s,t,x = map(int,input().split())
	evt.append((s-x,1,x))
	evt.append((t-x,-1,x))
q = []
ans = [0 for i in range(Q)]
for i in range(Q):
	d = int(input())
	q.append((-d, i))
q.sort()
evt.sort()

s = set([INF])
q_head = q.pop()
cnt = 0
for e in evt:
	if -q_head[0] < e[0]:
		ans[q_head[1]] = min(s)
		cnt += 1
		if cnt < Q:
			q_head = q.pop()
		else:
			break
	if e[1] == 1:
		s.add(e[2])
	elif e[1] == -1:
		s.remove(e[2])

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

Submission status: Wrong Answer

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

s = set([INF])
q_head = q.pop()
cnt = 0
for e in evt:
	if -q_head[0] < e[0]:
		ans[q_head[1]] = min(s)
		cnt += 1
		if cnt < Q:
			q_head = q.pop()
		else:
			break
	if e[1] == 1:
		s.add(e[2])
	elif e[1] == -1:
		s.remove(e[2])

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

Submission status: Wrong Answer

Solution code:
import collections


def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

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

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

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

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    N, Q = [int(x) for x in input().split()]
    updates1 = []
    updates2 = []
    for i in range(N):
        S, T, X = [int(x) for x in input().split()]
        updates1.append((S - X, X))
        updates2.append((T - X, X))

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

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

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
x_dict = {}
max_x = 0
for e in s[1:N + 1]:
    S, T, X = map(int, e.split())
    if X in x_dict:
        for i in range(S - 1, T):
            x_dict[X].add(i + 0.5)
    else:
        x_dict[X] = {S - 0.5}
        for i in range(S, T):
            x_dict[X].add(i + 0.5)
    if max_x < X:
        max_x = X
for e in s[N + 1:]:
    D = int(e)
    inf_flg = 1
    for x_place, x_time_set in x_dict.items():
        time = D + x_place + 0.5
        if time in x_time_set:
            print(x_place)
            inf_flg = 0
            break
    if inf_flg == 1:
        print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

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

S = defaultdict(int)
X = dict()

for i in range(N):
    s, t, x = list(map(int, input().split()))
    S[s - x] += 1
    S[t - x] -= 1

    if s - x not in X.keys() or X[s - x] > x:
        X[s - x] = x
    if t - x not in X.keys() or X[t - x] > x:
        X[t - x] = x


S = [(key, S[key]) for key in sorted(S.keys()) if S[key] != 0]

S += [(1e9+7, 0)]

idx = 0
cum = 0
for i in range(Q):
    D = int(input())
    while S[idx][0] <= D:
        cum += S[idx][1]
        idx += 1
    if cum == 0:
        print("-1")
    else:
        print(X[S[idx][0]])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

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

S = defaultdict(int)
X = dict()

for i in range(N):
    s, t, x = list(map(int, input().split()))
    S[s - x] += 1
    S[t - x] -= 1

    if s - x not in X.keys() or X[s - x] > x:
        X[s - x] = x
    if t - x not in X.keys() or X[t - x] > x:
        X[t - x] = x


S = [(key, S[key]) for key in sorted(S.keys()) if S[key] != 0]
print(S, X)

S += [(1e9+7, 0)]

idx = 0
cum = 0
for i in range(Q):
    D = int(input())
    while S[idx][0] <= D:
        cum += S[idx][1]
        idx += 1
    if cum == 0:
        print("-1")
    else:
        print(X[S[idx][0]])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
SmXTmXX = [0] * N
for i in range(N):
    s, t, x = map(int, input().split())
    SmXTmXX[i] = (s - x, t - x, x)
SmXTmXX.sort(key=lambda x: x[2], reverse=True)
# print(SmXTmXX)
D = np.zeros(Q)
for i in range(Q):
    d = int(input())
    D[i] = d

ans = np.full(Q, -1)
i = 0
for n in range(N):
    di, dj, x = SmXTmXX[n]
    if dj <= 0:
        continue
    i = np.searchsorted(D, di) if di > 0 else 0
    j = np.searchsorted(D, dj)
#     print(f"{i} to {j} is out")
    ans[i:j] = x
    # print(f"marked {k} as {x}")
for v in ans:
    print(v)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = [int(line) for line in lines[n:]]
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    if ss == tt:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

N, K = map(int, input().split())
V = list(map(int, input().split())) # N


ans = 0
for i in range(K+1):
  hand = V[:i]
  for j in range(K-i+1):
    if j != 0:
      x = hand + V[max(K-j, i):]
    else:
      x = hand
    rest = K - i - j
    summ = sum(v for i, v in enumerate(sorted(x)) if i >= rest or v > 0)
    ans = max(ans, summ)
    # print(f"K={K}, i={i}, j={j}, rest={rest}, sum={summ}, x={x}")
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = [int(line) for line in lines[n:]]
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    if tt == 0 or ss == q:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
s_t_q = []
d = []
for i in range(n):
    s_t_q.append(list(map(int, input().split())))
for i in range(q):
    d.append([int(input()), 0, True])
    
for i in range(len(s_t_q)):
    s_t_q[i].append(s_t_q[i][0]*s_t_q[i][2])

for s, t, x, sx in sorted(s_t_q, key=lambda x:x[3]):
    for i in range(len(d)):
        if d[i][2]:
            if s - d[i][0] <= x and t - d[i][0] > x:
                d[i][1] = x
                d[i][2] = False

for i, dist, flag in d:
    if flag:
        print(-1)
    else:
        print(dist)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from bisect import bisect,bisect_left
N,Q=map(int,input().split())
table=[]
for i in range(N):
    s,t,x=map(int,input().split())
    #print((max(0,s-x),t-1-x))
    table.append((x,s-x,t-x))
H=[]
D=[int(input()) for i in range(Q)]
#print(D)
for x,a,b in table:
    #print(x,a,b,(x,bisect_left(D,a),bisect(D,b)))
    heappush(H,(bisect_left(D,a),bisect_left(D,b),x))
#print(H)
K=[]
U=[10**12]*Q
J=[]
for i in range(Q):
    while len(J)>0 and J[0][2]<=i:
        y,u,v=heappop(J)
    while len(H)>0 and H[0][0]<=i:
        a,b,x=heappop(H)
        heappush(J,(x,a,b))
    if len(J)>0:
        U[i]=J[0][0]
    #print(i,J,H,U[i])
for i in range(Q):
    if U[i]==10**12:
        print(-1)
    else:
        print(U[i])

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())

mem = []

for i in range(N):
    s, t, x = map(int, input().split())
    mem.append((x, s-x, t-x))

mem.sort()

f = 0
for i in range(Q):
    d = int(input())
    ans = -1
    for j in range(f, N):
        if mem[j][1] <= d < mem[j][2]:
            ans = mem[j][0]
            f = j
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from bisect import bisect,bisect_left
N,Q=map(int,input().split())
table=[]
for i in range(N):
    s,t,x=map(int,input().split())
    if t-1-x<0:
        continue
    #print((max(0,s-x),t-1-x))
    table.append((x,max(0,s-x),t-1-x))
H=[]
D=[int(input()) for i in range(Q)]
#print(D)
# N: 処理する区間の長さ

INF = 2**31-1

LV = (Q-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for x,a,b in table:
    update(bisect_left(D,a),bisect(D,b),x)
for i in range(Q):
    if query(i,i+1)==2**31-1:
        print(-1)
    else:
        print(data[i])

Submission status: Wrong Answer

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

N, Q = list(map(int, input().split()))
S = dict()

for i in range(N):
    s, t, x = list(map(int, input().split()))
    if (s - x) in S.keys():
        S[s - x] = (lambda y: (y[0] + 1, min(y[1], x)))(S[s - x])
    else:
        S[s-x] = (1, x)
    if (t - x) in S.keys():
        S[t - x] = (lambda y: (y[0] - 1, min(y[1], x)))(S[t - x])
    else:
        S[t-x] = (-1, x)

S = [(lambda x,v:(x,v[0],v[1]) )  (key, S[key]) for key in sorted(S.keys())]
S += [(1e9+7, 0, 0)]

idx = 0
cum = 0
for i in range(Q):
    D = int(input())
    while S[idx][0] <= D:
        cum += S[idx][1]
        idx += 1
    if cum == 0:
        print("-1")
    else:
        print(S[idx][2])

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
w=[]
for i in range(n):
    w.append([int(i) for i in input().split()])
w=sorted(w,key=lambda x : x[0])
for i in range(q):
    d=int(input())
    for j in w:
        if j[0]<=d+j[2]<j[1]:
            print(j[2])
            break
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
x_dict = {}
max_x = 0
for e in s[1:N]:
    S, T, X = map(int, e.split())
    if X in x_dict:
        for i in range(S - 1, T):
            x_dict[X].add(i + 0.5)
    else:
        x_dict[X] = {S - 0.5}
        for i in range(S, T):
            x_dict[X].add(i + 0.5)
    if max_x < X:
        max_x = X
for e in s[N + 1:]:
    D = int(e)
    place = 0
    inf_flg = 1
    for i in range(max_x + 1):
        time = D + i + 0.5
        if place in x_dict:
            if time in x_dict[place]:
                print(place)
                inf_flg = 0
                break
        place += 1
    if inf_flg == 1:
        print(-1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
SmXTmXX = [0] * N
for i in range(N):
    s, t, x = map(int, input().split())
    SmXTmXX[i] = (s - x, t - x, x)
SmXTmXX.sort(key=lambda x: x[0])
# print(SmXTmXX)
D = [0] * Q
for i in range(Q):
    d = int(input())
    D[i] = d

ans = [-1] * Q
i = 0
for n in range(N):
    di, dj, x = SmXTmXX[n]
    if dj <= 0:
        continue
    i = bisect_left(D, di, i) if di > 0 else 0
    j = bisect_left(D, dj, i)
#     print(f"{i} to {j} is out")
#     for k in range(i, j):
    # ans[k] = x if ans[k] == -1 else min(ans[k], x)
    # print(f"marked {k} as {x}")
for v in ans:
    print(v)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
 
 
def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    def bsearch_l(val, D):
        l = -1
        r = Q - 1
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val > m:
                l = m
            else:
                r = m
        #print(val, l, r)
        return r
    def bsearch_r(val, D):
        l = 0
        r = Q
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val < D[m]:
                r = m
            else:
                l = m
        #print(val, l, r)
        return l
    a = []
    for i in range(N):
        a.append([X[i], max(0, -(X[i] - S[i]) - 1), max(0, -(X[i] - T[i]) - 1)])
    a.sort(key=lambda x: x[0])
    ret = [-1] * Q
    for tmp in a:
        l = bsearch_l(tmp[1], D)
        r = bsearch_r(tmp[2], D)
        #print(tmp)
        #print(l, r)
        for i in range(l, r + 1):
            if i >= 0 and i < Q and ret[i] < 0:
                ret[i] = tmp[0]
 
    for r in ret:
        print(r)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]" 
    T = [int()] * (N)  # type: "List[int]" 
    X = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(N, Q, S, T, X, D)
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    def bsearch_l(val, D):
        l = -1
        r = Q - 1
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val > m:
                l = m
            else:
                r = m
        #print(val, l, r)
        return r
    def bsearch_r(val, D):
        l = 0
        r = Q
        while r - l > 1:
            m = (l + r) // 2
            #print(val, l, r, m)
            if val < D[m]:
                r = m
            else:
                l = m
        #print(val, l, r)
        return l
    a = []
    for i in range(N):
        a.append([X[i], max(0, -(X[i] - S[i]) - 1), max(0, -(X[i] - T[i]) - 1)])
    a.sort(key=lambda x: x[0])
    ret = [-1] * Q
    for tmp in a:
        l = bsearch_l(tmp[1], D)
        r = bsearch_r(tmp[2], D)
        #print(tmp)
        #print(l, r)
        for i in range(l, r + 1):
            if i >= 0 and i < Q and ret[i] < 0:
                ret[i] = tmp[0]

    for r in ret:
        print(r)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]" 
    T = [int()] * (N)  # type: "List[int]" 
    X = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [ int(next(tokens)) for _ in range(Q) ]  # type: "List[int]"
    solve(N, Q, S, T, X, D)

if __name__ == '__main__':
    main()