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 sys
from bisect import bisect_right
from collections import deque

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

SmX = []
TmX = []
Id2SmX = {}
SmX2TminusXandX = {}
SmX2X = {}
TmX2X = {}
for i in range(N):
    s,t,x = list(map(int, input().split()))
    SmX2X[s-x] = x
    TmX2X[t-x] = x
    SmX.append(s-x)
    TmX.append(t-x)

SmX.sort()
TmX.sort()


D = deque([])
for i in range(Q):
    d = int(input())
    D.append(d)


def find_closed(d):
    i = bisect_right(SmX, d)
    Xs = set([SmX2X[s] for s in SmX[:i]])
    #print(i, Xs)
    j = bisect_right(TmX, d)
    Xt = set([TmX2X[t] for t in TmX[j:]])
    #print(j, Xt)
    Xst = Xs & Xt
    #print(Xst)
    xmin = 1000000000
    for x in Xst:
        xmin = min(xmin, x)
    if xmin == 1000000000:
        print(-1)
    else:
        print(x)

for j in range(Q):
    d = D.popleft()
    find_closed(d)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
N,Q = list(map(int,input().split(" ")))

hitos = []
ans = [-1] * Q
queries =[]
heapq.heapify(queries)
events = []
heapq.heapify(events)

for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append((lt,-1,X)) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所
    queries.append((rt,1,X)) # 1 → 削除クエリ



for i in range(Q):
    t = int(input())
    queries.append((t,0,-99)) # 0 → チェッククエリ
queries.sort(key = lambda x:x[0])
for t,kind,x in queries:
    if kind == 0:
        if len(events) > 0:
            print(events[0])
        else:
            print(-1)
    if kind == -1:
        heapq.heappush(events,x)
    if kind == 1:
        events.remove(x)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,q = LI()
    a = LIR(n)
    a.sort(key = lambda x : x[2])
    d = IR(q)
    ans = [-1]*q
    right = [0]*q
    for s,t,x in a:
        l = bisect.bisect_left(d,s-x)
        r = bisect.bisect_left(d,t-x)
        while r > l:
            if ans[l] != -1:
                l = right[l]
            if l > r:
                break
            ans[l] = x
            right[l] = r+1
            l += 1
    print(*ans, sep = "\n")
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,q = LI()
    a = LIR(n)
    a.sort(key = lambda x : x[2])
    d = IR(q)
    ans = [-1]*q
    right = [0]*q
    for s,t,x in a:
        l = bisect.bisect_left(d,s-x)
        r = bisect.bisect_left(d,t-x)
        while r > l:
            if ans[l] != -1:
                l = right[l]
            if l >= r:
                break
            ans[l] = x
            right[l] = r+1
            l += 1
    print(*ans, sep = "\n")
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, Q = map(int, input().rstrip().split())
S, T, X = (
    zip(*(map(int, input().rstrip().split()) for _ in range(N))) if N else
    ((), (), ())
)
D = [int(input()) for _ in range(Q)]

INF = 10**20

# 各時間帯について、その時間帯に出発すると影響を受ける工事を前もって求める
# 前もって求めた時間帯→工事を用いて、各クエリに回答する
C = sorted(
    [(s - x, x, 1) for s, x in zip(S, X)] +
    [(t - x, x, 0) for t, x in zip(T, X)]
)
q = [INF]
R = set()
u = []
v = []
for t, x, k in C:
    if k == 1:
        if x < q[0]:
            u.append(t)
            v.append(q[0])
        heappush(q, x)
    else:
        R.add(x)
        if x == q[0]:
            u.append(t)
            v.append(q[0])
        while q[0] in R:
            R.remove(heappop(q))
u.append(INF)
v.append(INF)

Y = []
i = 0
for d in D:
    while u[i] <= d:
        i += 1
    Y.append(v[i])

ans = '\n'.join(
    '-1' if y == INF else
    str(y)
    for y in Y
)
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def main():
    N, Q = map(int, input().split())
    S, T, X = (
        zip(*(map(int, input().split()) for _ in range(N))) if N else
        ((), (), ())
    )
    D = [int(input()) for _ in range(Q)]

    INF = 10**20

    # 各時間帯について、その時間帯に出発すると影響を受ける工事を前もって求める
    # 前もって求めた時間帯→工事を用いて、各クエリに回答する
    C = sorted(
        [(s - x, x, 1) for s, x in zip(S, X)] +
        [(t - x, x, 0) for t, x in zip(T, X)]
    )
    q = [INF]
    R = set()
    u = []
    v = []
    for t, x, k in C:
        if k == 1:
            if x < q[0]:
                u.append(t)
                v.append(q[0])
            heappush(q, x)
        else:
            R.add(x)
            if x == q[0]:
                u.append(t)
                v.append(q[0])
            while q[0] in R:
                R.remove(heappop(q))
    u.append(INF)
    v.append(INF)

    Y = []
    i = 0
    for d in D:
        while u[i] <= d:
            i += 1
        Y.append(v[i])

    ans = '\n'.join(
        '-1' if y == INF else
        str(y)
        for y in Y
    )
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

N, Q = map(int, input().split())
S, T, X = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), (), ())
)
D = [int(input()) for _ in range(Q)]

INF = 10**20

# 各時間帯について、その時間帯に出発すると影響を受ける工事を前もって求める
# 前もって求めた時間帯→工事を用いて、各クエリに回答する
C = sorted(
    [(s - x, x, 1) for s, x in zip(S, X)] +
    [(t - x, x, 0) for t, x in zip(T, X)]
)
q = [INF]
R = set()
u = []
v = []
for t, x, k in C:
    if k == 1:
        if x < q[0]:
            u.append(t)
            v.append(q[0])
        heappush(q, x)
    else:
        R.add(x)
        if x == q[0]:
            u.append(t)
            v.append(q[0])
        while q[0] in R:
            R.remove(heappop(q))
u.append(INF)
v.append(INF)

Y = []
i = 0
for d in D:
    while u[i] <= d:
        i += 1
    Y.append(v[i])

ans = '\n'.join(
    '-1' if y == INF else
    str(y)
    for y in Y
)
print(ans)

Submission status: Wrong Answer

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


N, Q = map(int, input().split())
S, T, X = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), (), ())
)
D = [int(input()) for _ in range(Q)]

INF = 10**20

# 各時間帯について、その時間帯に出発すると影響を受ける工事を前もって求める
# 前もって求めた時間帯→工事を用いて、各クエリに回答する
C = sorted(
    [(s - x, x, 1) for s, x in zip(S, X)] +
    [(t - x, x, 0) for t, x in zip(T, X)]
)
q = [INF]
R = set()
u = []
v = []
for t, x, k in C:
    if k == 1:
        if x < q[0]:
            u.append(t)
            v.append(q[0])
        heappush(q, x)
    else:
        R.add(x)
        if x == q[0]:
            u.append(t)
            v.append(q[0])
        while q[0] in R:
            R.remove(heappop(q))
v.append(INF)

ans = '\n'.join(
    '-1' if y == INF else
    str(y)
    for y in (
        v[bisect(u, d)]
        for d in D
    )
)
print(list(zip(u, v)))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    bisect.insort(STX, (X, S, T))

kensaku = dict()
for i in range(Q):
    D.append(int(input()))
    kensaku[D[-1]] = i

dist = [10000000000000 for i in range(Q)]

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    for j in range(a, b):
        dist[kensaku[D[j]]] = min(dist[kensaku[D[j]]], X)
    del D[a:b]

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    STX.append(list(map(int, input().split())))
STX.sort(key=lambda x: x[2])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    STX.append(list(map(int, input().split())))
STX.sort(key=lambda x: x[0])

kensaku = dict()
for i in range(Q):
    D.append(int(input()))
    kensaku[D[-1]] = i

dist = [10000000000000 for i in range(Q)]

for i in range(N):
    s = STX[i][0] - STX[i][2]
    t = STX[i][1] - STX[i][2] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    for j in range(a, b):
        dist[kensaku[D[j]]] = min(dist[kensaku[D[j]]], STX[i][2])
    del D[a:b]


for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Wrong Answer

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# random_denseがTLE, 他はAC
"""
from bisect import bisect_left, bisect_right  # 二分探索
def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)
"""

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み

    events = []
    for s, t, x in STX:
        events.append(('S', s-x-0.25, x))
        events.append(('T', t-x-0.75, x))  # 0.5 同士だと [1, 2), [0, 1) で吹き飛ぶ
    for i, d in enumerate(D):
        events.append(('D', d, i))
    
    ans = [-1] * Q
    events.sort(key=lambda v: v[1])
    xset = set()
    xmin = None
    #xmin = 1e+10
    #xb = False
    for event, time, xi in events:
        if event == 'S':
            xset.add(xi)
            if xmin is None:
                xmin = xi
            elif xmin > xi:
                xmin = xi
                #xb = True
        elif event == 'T':
            xset.remove(xi)
            if xmin == xi:
                xmin = None
                #xb = False
        elif event == 'D' and xset:
            #if not xb:
            if xmin is None:
                xmin = min(xset)
                #xb = True
            ans[xi] = xmin

    for n in ans:
        print(n)

main()

Submission status: Wrong Answer

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# random_denseがTLE, 他はAC
from bisect import bisect_left, bisect_right  # 二分探索
def main_tle():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み

    events = []
    for i, d in enumerate(D):
        events.append((d, 'D', i))
    for s, t, x in STX:
        events.append((s-x-0.4, 'S', x))
        events.append((t-x-0.6, 'T', x))  # 0.5 同士だと [1, 2), [0, 1) で吹き飛ぶ
    
    ans = [-1] * Q
    #events.sort(key=lambda v: v[1])
    events.sort(key=lambda v: v[0])
    xset = set()
    xmin = None
    for time, event, xi in events:
        if event == 'S':
            xset.add(xi)
            if xmin is None or xmin > xi:
                xmin = xi
        elif event == 'T':
            xset.remove(xi)
            if xmin == xi:
                xmin = None
        elif event == 'D' and xset:
            if xmin is None:
                xmin = min(xset)
            ans[xi] = xmin

    for n in ans:
        print(n)

main()

Submission status: Wrong Answer

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# random_denseがTLE, 他はAC
from bisect import bisect_left, bisect_right  # 二分探索
def main_tle():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み

    events = []
    for i, d in enumerate(D):
        events.append((d, 'D', i))
    for s, t, x in STX:
        events.append(((s-x-0.4), 'S', x))
        events.append(((t-x-0.6), 'T', x))  # 0.5 同士だと [1, 2), [0, 1) で吹き飛ぶ
    
    ans = [-1] * Q
    #events.sort(key=lambda v: v[1])
    events.sort()
    xset = set()
    xmin = None
    error = 0
    for event, time, xi in events:
        if event == 'S':
            xset.add(xi)
            if xmin is None or xmin > xi:
                xmin = xi
        elif event == 'T':
            if xi not in xset:
                error += 1
                continue
            xset.remove(xi)
            if xmin == xi:
                xmin = None
        elif event == 'D' and xset:
            if xmin is None:
                xmin = min(xset)
            ans[xi] = xmin

    for n in ans:
        print(n)

main()

Submission status: Wrong Answer

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# random_denseがTLE, 他はAC
from bisect import bisect_left, bisect_right  # 二分探索
def main_tle():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み

    events = []
    for i, d in enumerate(D):
        events.append(('D', d, i))
    for s, t, x in STX:
        events.append(('S', (s-x-0.4), x))
        events.append(('T', (t-x-0.6), x))  # 0.5 同士だと [1, 2), [0, 1) で吹き飛ぶ
    
    ans = [-1] * Q
    events.sort(key=lambda v: v[1])
    xset = set()
    xmin = None
    error = 0
    for event, time, xi in events:
        if event == 'S':
            xset.add(xi)
            if xmin is None or xmin > xi:
                xmin = xi
        elif event == 'T':
            if xi not in xset:
                error += 1
                continue
            xset.remove(xi)
            if xmin == xi:
                xmin = None
        elif event == 'D' and xset:
            if xmin is None:
                xmin = min(xset)
            ans[xi] = xmin

    for n in ans:
        print(n)

main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]
ans=defaultdict(lambda: -1) 

while roadwork:
	x,s,t=heappop(roadwork)

	modosu=[]
	while pending:
		pd=heappop(pending)
		if s<=pd<=t:
			ans[pd]=x
		else:
			modosu.append(pd)
			if t<pd:
				break
	for pd in modosu:
		heappush(pending,pd)

	while dhq:
		d=heappop(dhq)
		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )
			if t<d:
				break
	else:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]
ans=defaultdict(lambda: -1) 

while roadwork:
	x,s,t=heappop(roadwork)

	modosu=[]
	while pending:
		pd=heappop(pending)
		if s<=pd<=t:
			ans[pd]=x
		else:
			modosu.append(pd)
	else:
		for m in modosu:
			heappush(pending,m)


	while dhq:
		d=heappop(dhq)
		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )
			if t<d:
				break
	else:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]
ans=defaultdict(lambda: -1) 

while roadwork:
	x,s,t=heappop(roadwork)

	modosu=[]
	while pending:
		pd=heappop(pending)
		if s<=pd<=t:
			ans[pd]=x
		else:
			modosu.append(x)
	else:
		for m in modosu:
			heappush(pending,m)


	while dhq:
		d=heappop(dhq)
		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )
			if t<d:
				break
	else:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]
ans=defaultdict(lambda: -1) 

while roadwork:
	x,s,t=heappop(roadwork)

	modosu=[]
	while pending:
		pd=heappop(pending)
		if s<=pd<=t:
			ans[pd]=x
		else:
			modosu.append(pd)
			if t<d:
				break
	for pd in modosu:
		heappush(pending,pd)

	while dhq:
		d=heappop(dhq)
		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )
			if t<d:
				break
	else:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()
print "roadwork :::: ",roadwork

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]
ans=defaultdict(lambda: -1) 

while roadwork:
	x,s,t=heappop(roadwork)

	modosu=[]
	while pending:
		pd=heappop(pending)
		if s<=pd<=t:
			ans[pd]=x
		else:
			modosu.append(pd)
			if t<d:
				break
	for pd in modosu:
		heappush(pending,pd)

	while dhq:
		d=heappop(dhq)
		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )
			if t<d:
				break
	else:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]

ans=defaultdict(lambda: -1) 


while roadwork:
	x,s,t=heappop(roadwork)

	while pending:
		pd=heappop(pending)
		if s<=pd<=t:
			ans[pd]=x

	while dhq:
		d=heappop(dhq)
		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )

		if t<d:
			break
	else:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]

ans=defaultdict(lambda: -1) 


while roadwork:
	x,s,t=heappop(roadwork)

	while pending:
		pd=heappop(pending)
		if s<=pd<=t:
			ans[pd]=x
		else:
			heappush(pending, pd)
			break
	while dhq:
		d=heappop(dhq)
		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )

		if t<d:
			break
	else:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]

ans=defaultdict(lambda: float("inf")) 


while roadwork:
	x,s,t=heappop(roadwork)
	while dhq:
		d=heappop(dhq)
		while pending:
			pd=heappop(pending)
			if s<=pd<=t:
				ans[pd]=min(ans[pd], x)
			else:
				heappush(pending, pd)
				break

		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )

		if t<d:
			break

	if not dhq:
		break


for d in D:
	if ans[d]==float("inf"):
		print -1
	else:
		print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]

ans=defaultdict(lambda: -1) 


while roadwork:
	x,s,t=heappop(roadwork)
	while dhq:
		d=heappop(dhq)
		while pending:
			pd=heappop(pending)
			if s<=pd<=t:
				ans[pd]=x
			else:
				heappush(pending, pd)
				break

		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )

		if t<d:
			break

	if not dhq:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
roadwork=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	roadwork.append(  (x, max(0,s-x) , max(0,t-1-x)) )

roadwork.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
dhq=copy.deepcopy(D)
heapify(dhq)

pending=[]

ans=defaultdict(lambda: -1) 


while roadwork:
	x,s,t=heappop(roadwork)
	while dhq:
		d=heappop(dhq)
		modosu=[]
		while pending:
			pd=heappop(pending)
			if s<=pd<=t:
				ans[pd]=x
			else:
				modosu.append(pd)
		else:
			for pd in modosu:
				heappush(pending,pd)

		if s<=d<=t:
			ans[d]=x
		else:
			heappush(pending ,d )

		if t<d:
			break

	if not dhq:
		break


for d in D:
	print ans[d]

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify

N,Q=map(int, sys.stdin.readline().split())

RW=[]	#  Roadwork: 道路工事を行っている場所　(開始時間、終了時間、x座標)
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( RW, (max(0,s-x) , max(0,t-1-x),x) )


D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]	# Q人の歩き出す時刻
D.sort()


d=0
for d in D:
	hq=[]
	for s,t,x in RW:
		if s<=d<=t:
			heappush(hq, x)
		elif t<d:
			heappop(RW)

	if hq:
		print hq[0]
	else:
		print -1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify

N,Q=map(int, sys.stdin.readline().split())

RW=[]	#  Roadwork: 道路工事を行っている場所　(開始時間、終了時間、x座標)
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( RW,(max(0,s-x) , max(0,t-1-x),x) )

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]	# Q人の歩き出す時刻
D.sort()


d=0
for d in D:
	hq=[]
	for s,t,x in RW:
		if s<=d<=t:
			heappush(hq, x)
		elif t<d:
			heappop(RW)

	try:
		print hq[0]
	except:
		print -1