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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

input = sys.stdin.readline

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))
    E.sort(reverse=True)

    q = []
    done = set()
    ans = [-1] * Q
    for j, d in enumerate(D):
        while E and E[-1][0] <= d:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, x)
            else:
                done.add(x)

        while q and q[0] in done:
            done.remove(heapq.heappop(q))

        if q:
            ans[j] = q[0]

    for i in range(Q):
        print(ans[i])


def main():
    N, Q = read_int_n()
    STX = tuple(read_int_n() for _ in range(N))
    D = tuple(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

input = sys.stdin.readline

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x))
        E.append((t-x, -1, x))
    E.sort(reverse=True)

    q = []
    done = set()
    ans = [-1] * Q
    for j, d in enumerate(D):
        while E and E[-1][0] <= d:
            t, e, x = E.pop()
            if e == 1:
                heapq.heappush(q, x)
            else:
                done.add(x)

        while q and q[0] in done:
            done.remove(heapq.heappop(q))

        if q:
            ans[j] = q[0]

    for i in range(Q):
        print(ans[i])


def main():
    N, Q = read_int_n()
    STX = tuple(read_int_n() for _ in range(N))
    D = tuple(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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:
  q.append((s-x,1,x)) # xで死ぬ
  q.append((t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

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

q.sort()

for a,c,b in q:
  if not c:
    se.remove(b)
  elif c&1:
    se.add(b)
  #else:
  #  if se:
  #    answer[b] = min(se)

print('\n'.join(map(str,answer)))

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で死ななくなる

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

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

while q:
  a,c,b = heappop(q)
  if not c:
    se.remove(b)
  elif c&1:
    se.add(b)
  #else:
  #  if se:
  #    answer[b] = min(se)

print('\n'.join(map(str,answer)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

input = sys.stdin.readline

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))

    E.sort(reverse=True)

    q = []
    done = set()
    D = [(i, d) for i, d in enumerate(D)]
    D.sort(reverse=True)
    ans = [-1] * Q
    while D:
        while E and E[-1][0] <= D[-1][1]:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, (x, i))
            else:
                done.add((x, i))

        while q and q[0] in done:
            heapq.heappop(q)

        i, d = D.pop()
        if q and q[0][0] > d:
            ans[i] = q[0][0]

    for i in range(Q):
        print(ans[i])


def main():
    N, Q = read_int_n()
    STX = tuple(read_int_n() for _ in range(N))
    D = tuple(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))

    # N = 2 * (10**5)
    # Q = 2 * (10**5)
    # STX = []
    # for _ in range(N):
    #     s = random.randint(0, 10**9)
    #     t = random.randint(0, 10**9)
    #     if s > t:
    #         s, t = t, s
    #     x = random.randint(0, 10**9)
    #     STX.append((s, t, x))
    # D = [random.randint(0, 10**9) for _ in range(Q)]
    # (slv(N, Q, STX, D))

    # print(N, Q)
    # for s, t, x in STX:
    #     print(s, t, x)
    # for d in D:
    #     print(d)


if __name__ == '__main__':
    main()

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で死ななくなる

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = []
remove_task = []

while q:
  a,c,b = heappop(q)
  if not c:
    heappush(remove_task,b)
  elif c&1:
    heappush(se,b)
  #else:
  #  while remove_task and (se[0] == remove_task[0]):
  #    heappop(se)
  #    heappop(remove_task)
  #  if se:
  #    answer[b] = se[0]
  #print(a,c,b,se,remove_task)
print('\n'.join(map(str,answer)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

input = sys.stdin.readline

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))

    E.sort(reverse=True)

    q = []
    done = set()
    D = [(i, d) for i, d in enumerate(D)]
    D.sort(reverse=True)
    ans = [-1] * Q
    while D:
        while E and E[-1][0] <= D[-1][1]:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, (x, i))
            else:
                done.add((x, i))

        while q and q[0] in done:
            heapq.heappop(q)

        i, d = D.pop()
        if q and q[0][0] >= d:
            ans[i] = q[0][0]

    for i in range(Q):
        print(ans[i])


def main():
    N, Q = read_int_n()
    STX = tuple(read_int_n() for _ in range(N))
    D = tuple(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))

    # N = 2 * (10**5)
    # Q = 2 * (10**5)
    # STX = []
    # for _ in range(N):
    #     s = random.randint(0, 10**9)
    #     t = random.randint(0, 10**9)
    #     if s > t:
    #         s, t = t, s
    #     x = random.randint(0, 10**9)
    #     STX.append((s, t, x))
    # D = [random.randint(0, 10**9) for _ in range(Q)]
    # (slv(N, Q, STX, D))

    # print(N, Q)
    # for s, t, x in STX:
    #     print(s, t, x)
    # for d in D:
    #     print(d)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        XST.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [INF] * len(D)
    for x, s, t in XST:
        s0 = bisect_left(D, s - x)
        t0 = bisect_left(D, t - x)
        for i in range(s0, t0):
            ans[i] = min(ans[i], x)
    for y in ans:
        print(-1 if y == INF else y)
    return

main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, Q = map(int, input().split())
tl = []
for i in range(N):
    S, T, X = map(int, input().split())
    tl.append([S-X, '1S', X])
    tl.append([T-X, '0T', X])
d = []
for i in range(Q):
    D = int(input())
    tl.append([D, '2D'])

tl.sort()
#print(tl)

ans = []
Xhp = []
dX = set()
for t in tl:
    mode = t[1]
    if mode == '1S':
        X = t[2]
        if X in dX:
            dX.remove(X)
        heappush(Xhp, X)
    elif mode == '0T':
        X = t[2]
        dX.add(X)
    else:
        while True:
            if not Xhp:
                ans.append(-1)
                break
            Xmin = heappop(Xhp)
            if Xmin in dX:
                dX.remove(Xmin)
                continue
            else:
                ans.append(Xmin)
                break

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, Q = map(int, input().split())
tl = []
for i in range(N):
    S, T, X = map(int, input().split())
    tl.append([S-0.25-X, 'S', X])
    tl.append([T-0.75-X, 'T', X])
d = []
for i in range(Q):
    D = int(input())
    tl.append([D, 'D'])

tl.sort()
#print(tl)

ans = []
Xhp = []
deletedX = {}
for t in tl:
    mode = t[1]
    if mode == 'S':
        X = t[2]
        if str(X) in deletedX:
            deletedX.pop(str(X))
        heappush(Xhp, X)
    elif mode == 'T':
        X = t[2]
        deletedX[str(X)] = 1
    else:
        while True:
            if not Xhp:
                ans.append(-1)
                break
            Xmin = heappop(Xhp)
            if str(Xmin) in deletedX:
                deletedX.pop(str(Xmin))
                continue
            else:
                ans.append(Xmin)
                break

for a in ans:
    print(a)

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で死ななくなる

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

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

while q:
  a,c,b = heappop(q)
  if not c:
    se.remove(b)
  elif c&1:
    se.add(b)
  else:
    if se:
      answer[b] = 0#min(se)

print('\n'.join(map(str,answer)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))

    E.sort(reverse=True)

    q = []
    done = set()
    D = [(i, d) for i, d in enumerate(D)]
    D.sort(reverse=True)
    ans = [-1] * Q
    while D:
        while E and E[-1][0] <= D[-1][1]:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, (x, i))
            else:
                done.add((x, i))

        while q and q[0] in done:
            heapq.heappop(q)

        i, d = D.pop()
        if q and q[0][0] >= d:
            ans[i] = q[0][0]

    for i in range(Q):
        print(ans[i])


def main():
    N, Q = read_int_n()
    STX = [read_int_n() for _ in range(N)]
    D = [read_int() for _ in range(Q)]
    (slv(N, Q, STX, D))

    # N = 2 * (10**5)
    # Q = 2 * (10**5)
    # STX = []
    # for _ in range(N):
    #     s = random.randint(0, 10**9)
    #     t = random.randint(0, 10**9)
    #     if s > t:
    #         s, t = t, s
    #     x = random.randint(0, 10**9)
    #     STX.append((s, t, x))
    # D = [random.randint(0, 10**9) for _ in range(Q)]
    # (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))

    E.sort(reverse=True)

    q = []
    done = set()
    D = [(i, d) for i, d in enumerate(D)]
    D.sort(reverse=True)
    ans = [-1] * Q
    while D:
        while E and E[-1][0] <= D[-1][1]:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, (x, i))
            else:
                done.add((x, i))

        while q and q[0] in done:
            heapq.heappop(q)

        i, d = D.pop()
        if q and q[0][0] > d:
            ans[i] = q[0][0]

    for i in range(Q):
        print(ans[i])


def main():
    N, Q = read_int_n()
    STX = [read_int_n() for _ in range(N)]
    D = [read_int() for _ in range(Q)]
    (slv(N, Q, STX, D))

    # N = 2 * (10**5)
    # Q = 2*(10**5)
    # STX = []
    # for _ in range(N):
    #     s = random.randint(0, 10**9)
    #     t = random.randint(0, 10**9)
    #     if s > t:
    #         s, t = t, s
    #     x = random.randint(0, 10**9)
    #     STX.append((s, t, x))
    # D = [random.randint(0, 10**9) for _ in range(Q)]
    # (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
read = input 
rn = lambda :list(map(int, read().split()))
n, q = rn()
STX = [rn() for i in range(n)]
D = [rn()[0] for i in range(q)]
D = list(map(lambda tp:( -tp[1], tp[0],), enumerate(D)))# 相当于-d处0时出发 (-d, index)
         
D.sort()
STX.sort(key=lambda tp:tp[0]) # sort by -d
# O(n) zhuqufa
ans = [-1 for i in range(len(D))]
level = 0
while( (1<<level) < len(D)): # leaves cnt >= len(D)
    level += 1
tree = [(0,0) for i in range((1<<(level+1)) -1 )]
Dstart = (1<<level) - 1
Dend = (1<<level) - 1 + len(D)
# print(Dstart, Dend, len(tree), level)
for i in range(Dstart, Dend):
    ii = i
    i -= Dstart
    tree[ii] = [D[i][0],D[i][0], -1, D[i][1]]
for i in range(Dend, len(tree)):
    tree[i] = [D[-1][0],D[-1][0], 0] # [3] = 0,自动忽略
for i in range(Dstart - 1, 0-1,-1):
    l = i * 2 + 1
    r = i * 2 + 2
    tree[i] = [tree[l][0], tree[r][1], min(tree[l][2] , tree[r][2])]
def search(l,r,d,i): # [l,r] terminate at d
    if tree[i][2] >= 0:return # done
    if r < tree[i][0]:return
    if l > tree[i][1]:return
    if i >= Dend:return
    if i >= Dstart:
        tree[i][2] = d
        return
    lc = i * 2 + 1
    rc = i * 2 + 2
    search(l,r,d,lc)
    search(l,r,d,rc)
    tree[i][2] = min(tree[lc][2], tree[rc][2])
# print(tree[:Dstart])
# print(tree[Dstart:Dend])
# print(tree[Dend:])
for s,t,x in STX:
    t -= 1
    l = x -t 
    r = x - s
    search(l,r,x,0)
#     print('\n',l,r,x, [s,t,x])
#     print(tree[:Dstart])
#     print(tree[Dstart:Dend])
#     print(tree[Dend:])
for a,b,d,i in tree[Dstart: Dend]:
    ans[i] = d
for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, Q, STX, D):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))
        print(s-x, t-x)

    E.sort(reverse=True)

    q = []
    done = set()
    D = [(i, d) for i, d in enumerate(D)]
    D.sort(reverse=True)
    ans = [-1] * Q
    while D:
        while E and E[-1][0] <= D[-1][1]:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, (x, i))
            else:
                done.add((x, i))

        while q and q[0] in done:
            heapq.heappop(q)

        i, d = D.pop()
        if q and q[0][0] > d:
            ans[i] = q[0][0]

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


def main():
    N, Q = read_int_n()
    STX = [read_int_n() for _ in range(N)]
    D = [read_int() for _ in range(Q)]
    (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
read = input 
rn = lambda :list(map(int, read().split()))
n, q = rn()
STX = [rn() for i in range(n)]
D = [rn()[0] for i in range(q)]
D = list(map(lambda tp:( -tp[1], tp[0],), enumerate(D)))# 相当于-d处0时出发 (-d, index)
         
D.sort()
STX.sort(key=lambda tp:tp[0]) # sort by -d
# O(n) zhuqufa
ans = [-1 for i in range(len(D))]
level = 0
while( (1<<level) < len(D)): # leaves cnt >= len(D)
    level += 1
tree = [(0,0) for i in range((1<<(level+1)) -1 )]
Dstart = (1<<level) - 1
Dend = (1<<level) - 1 + len(D)
# print(Dstart, Dend, len(tree), level)
for i in range(Dstart, Dend):
    ii = i
    i -= Dstart
    tree[ii] = [D[i][0],D[i][0], -1, D[i][1]]
for i in range(Dend, len(tree)):
    tree[i] = [D[-1][0],D[-1][0], 0] # [3] = 0,自动忽略
for i in range(Dstart - 1, 0-1,-1):
    l = i * 2 + 1
    r = i * 2 + 2
    tree[i] = [tree[l][0], tree[r][1], min(tree[l][2] , tree[r][2])]
def search(l,r,d,i): # [l,r] terminate at d
    if tree[i][2] >= 0:return # done
    if r < tree[i][0]:return
    if l > tree[i][1]:return
    if i >= Dstart:
        tree[i][2] = d
        return
    lc = i * 2 + 1
    rc = i * 2 + 2
    search(l,r,d,lc)
    search(l,r,d,rc)
    tree[i][2] = min(tree[lc][2], tree[rc][2])
# print(tree[:Dstart])
# print(tree[Dstart:Dend])
# print(tree[Dend:])
for s,t,x in STX:
    t -= 1
    l = x -t 
    r = x - s
    search(l,r,x,0)
#     print('\n',l,r,x, [s,t,x])
#     print(tree[:Dstart])
#     print(tree[Dstart:Dend])
#     print(tree[Dend:])
for a,b,d,i in tree[Dstart: Dend]:
    ans[i] = d
for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

N, Q = map(int, input().split())
tl = []
for i in range(N):
    S, T, X = map(int, input().split())
    tl.append([S-X, 0, 'S', X])
    tl.append([T-X, 2, 'T', X])
d = []
for i in range(Q):
    D = int(input())
    tl.append([D, 1, 'D'])

tl.sort()

ans = []
Xhp = []
deletedX = {}
for t in tl:
    mode = t[2]
    if mode == 'S':
        X = t[3]
        heappush(Xhp, X)
    elif mode == 'T':
        X = t[3]
        deletedX[str(X)] = 1
    else:
        while True:
            if not Xhp:
                ans.append(-1)
                break
            Xmin = heappop(Xhp)
            if str(Xmin) in deletedX:
                deletedX.pop(str(Xmin))
                continue
            else:
                ans.append(Xmin)
                break

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
W = [[] for i in range(2 * N)]
Xd = dict()
for i in range(0, 2 * N, 2):
  S, T, X = map(int, input().split())
  W[i] = [S - X, X]
  W[i + 1] = [T - X, -X]
  Xd[X] = 0
rXd = [0] * len(Xd)
for i, k in enumerate(Xd.keys()):
  Xd[k] = i
  rXd[i] = k
ST = [0]
n = len(Xd) - 1
B = 0
while n:
  B += 1
  ST.append([0] * (2 ** B))
  n //= 2
W.sort()
def segAdd(a):
  ST[0] += 1
  for b in range(B):
    ST[B - b][a] += 1
    a //= 2
def segSub(a):
  ST[0] -= 1
  for b in range(B):
    ST[B - b][a] -= 1
    a //= 2
def segMin():
  if ST[0] == 0:
    return -1
  k = 0
  for b in range(B):
    k *= 2
    if ST[b + 1][k] == 0:
      k += 1
  return rXd[k]
for i in range(Q):
  D = int(input())
  if len(W):
    while W[0][0] <= D:
      w = W.pop(0)
      if w[1] > 0:
        segAdd(Xd[w[1]])
      else:
        segSub(Xd[-w[1]])
      if len(W) == 0:
        break
  print(segMin())

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heapify

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

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

event.sort()

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

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heapify

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

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

event.sort()

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

Submission status: 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 and J[0][1]<=i<J[0][2]:
        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())
W = [[] for i in range(2 * N)]
Xd = dict()
for i in range(0, 2 * N, 2):
  S, T, X = map(int, input().split())
  s = max(S - X, 0)
  t = max(T - X, 0)
  W[i] = [s, X]
  W[i + 1] = [t, -X]
  Xd[X] = 0
rXd = [0] * len(Xd)
for i, k in enumerate(Xd.keys()):
  Xd[k] = i
  rXd[i] = k
ST = [[0]]
n = len(Xd) - 1
B = 0
while n:
  B += 1
  ST.append([0] * (2 ** B))
  n //= 2
W.sort()
def segAdd(ST, a):
  ST[0][0] += 1
  for b in range(B):
    ST[B - b][a] += 1
    a //= 2
def segSub(ST, a):
  ST[0][0] -= 1
  for b in range(B):
    ST[B - b][a] -= 1
    a //= 2
def segMin(ST, rXd):
  if ST[0][0] == 0:
    return -1
  k = 0
  for b in range(B):
    k *= 2
    if ST[b + 1][k] == 0:
      k += 1
  return rXd[k]
for i in range(Q):
  D = int(input())
  if len(W):
    while W[0][0] <= D:
      w = W.pop(0)
      if w[1] > 0:
        segAdd(ST, Xd[w[1]])
      else:
        segSub(ST, Xd[-w[1]])
      if len(W) == 0:
        break
  print(segMin(ST, rXd))

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
events = []
for n in range(N):
  S,T,X = map(int,input().split())
  events.append([S-X,1,X])
  events.append([T-X,-1,X])
    
D = [int(input()) for _ in range(Q)]
events = sorted(events, key= lambda x:x[0])

points = set()
print(events)
itera = 0
for t in range(events[0][0],D[-1]+1):
  while events[itera][0] == t:
    if events[itera][1] == 1:
      points.add(events[itera][2])
    if events[itera][1] == -1:
      points.remove(events[itera][2])
      
    if itera < len(events) -1:
      itera += 1
    else:
      break
  if D[0] == t:
    if points == set():
      print(-1)
    else:
      print(min(points))
    D.pop(0)

Submission status: Wrong Answer

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