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: Accepted

Solution code:
from operator import itemgetter
import sys

input = sys.stdin.readline

inf = float('inf')

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

events = []
method_events_append = events.append

for _ in range(N):
    s, t, x = map(int, input().split())
    method_events_append((s - x, 1, x))  # add_event
    method_events_append((t - x, -1, x))  # remove_event

events.sort(key=itemgetter(0))  # イベント処理時刻昇順ソート

under_construction = set()
method_uc_add = under_construction.add
method_uc_discard = under_construction.discard

min_stop = inf
not_chg_flg = True

cur = 0
for _ in range(Q):
    d = int(input())
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        if event_type == 1:  # add_event
            method_uc_add(under_construction_x)
            if not_chg_flg:  # この分岐がないとdiscardされたmin_stopと比較する恐れがある
                min_stop = min(min_stop, under_construction_x)
        else:  # remove_event
            method_uc_discard(under_construction_x)
            if not_chg_flg and min_stop == under_construction_x:
                not_chg_flg = False
        cur += 1

    if not not_chg_flg:
        min_stop = min(under_construction) if under_construction else inf
        not_chg_flg = True
    print(min_stop if min_stop != inf else -1)

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys

input = sys.stdin.readline

inf = float('inf')

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

events = []

for _ in range(N):
    s, t, x = map(int, input().split())
    add_event = (s - x, 1, x)
    remove_event = (t - x, -1, x)
    events.append(add_event)
    events.append(remove_event)

events.sort(key=itemgetter(0))  # イベント処理時刻昇順ソート

under_construction = set()

min_stop = inf
chg_flg = False

cur = 0
for _ in range(Q):
    d = int(input())
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        if event_type == 1:  # add_event
            under_construction.add(under_construction_x)
            if not chg_flg:
                min_stop = min(min_stop, under_construction_x)
        else:  # remove_event
            under_construction.discard(under_construction_x)
            if not chg_flg and min_stop == under_construction_x:
                chg_flg = True
        cur += 1

    if chg_flg:
        min_stop = min(under_construction) if under_construction else inf
        chg_flg = False
    print(min_stop if min_stop != inf else -1)

Submission status: Accepted

Solution code:

def BinarySearchLowerBound(_arr, _ele): # arr is strictly increasing
    low_ind = 0
    up_ind = len(_arr) - 1
    if _arr[low_ind] >= _ele:
        return low_ind
    if _arr[up_ind] <= _ele:
        return up_ind + 1
    found = None
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append(int(raw_input()))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        lit = BinarySearchLowerBound(D, Li)
        rit = BinarySearchLowerBound(D, Ri)
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[lit] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = rit
                lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#ref : https://atcoder.jp/contests/abc128/submissions/5694292
#工事を座標順に処理，工事にぶつかる人をにぶたん
#すでに更新済みだったら更新しない．-> jumpで管理
from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
consts.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')

Submission status: Accepted

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

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,Q = ints_raw()
    origST = []

    for _  in range(N):
        S,T,X = ints_raw()
        origST.append([S-X,T-X,X])
    Ds = [int(input()) for _ in range(Q)]

    origST.sort()
    stidx = 0
    cur_set = []
    for d in Ds:

        while stidx < len(origST):
            st = origST[stidx]
            if st[0] > d:
                break
            heappush(cur_set,(st[2],st[1]))
            stidx+=1
        while cur_set and cur_set[0][1] <=d:
            heappop(cur_set)
        if cur_set:
            print(cur_set[0][0])
        else:
            print(-1)
main()

Submission status: Accepted

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

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,Q = ints_raw()
    origST = []

    for idx  in range(N):
        S,T,X = ints_raw()
        origST.append([S-X,T-X,X])
    Ds = [int(input()) for _ in range(Q)]

    origST.sort()
    stidx = 0
    cur_set = []
    for q in Ds:

        while stidx < len(origST):
            st = origST[stidx]
            if st[0] > q:
                break
            heappush(cur_set,(st[2],st[1]))
            stidx+=1
        while cur_set and cur_set[0][1] <=q:
            heappop(cur_set)
        if len(cur_set)==0:
            print(-1)
        else:
            print(cur_set[0][0])
main()

Submission status: Accepted

Solution code:
import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

Submission status: Accepted

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

n, q = map(int, input().split())
cons = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

cons.sort(key=lambda x: x[2])
for i in range(n):
    cons[i][0] -= cons[i][2]
    cons[i][1] -= cons[i][2]

ans = [-1] * q
l = [-1] * q
for i in range(n):
    s = bisect.bisect_left(d, cons[i][0])
    t = bisect.bisect_left(d, cons[i][1])
    while s < t:
        if l[s] != -1:
            s = l[s]
        else:
            ans[s] = cons[i][2]
            l[s] = t
            s += 1
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import bisect

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

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

list_xst.sort(key=lambda l:l[0])

list_d = [int(input()) for _ in range(q)]

retn = [-1] * q
jmp = [-1] * q

for x,s,t in list_xst:
    i = bisect.bisect_left(list_d, s)
    tt = bisect.bisect_left(list_d, t)
    while i < tt:
        if (jmp[i] != -1):
            i = jmp[i]
        else:
            retn[i] = x
            jmp[i] = tt
            i += 1

print(*retn, sep="\n")

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
from operator import itemgetter
class DammyMap:
    #1-indexed
    def __init__(self, A, B):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        #self.X, self.comp = self.compress(B)
        self.X = B[:]
        self.comp = {v : k for k, v in enumerate(D, 1)}
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.size)
    
    def count(self, i):
        #i(Bの元)以下の個数を取得
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        #iをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        # v番目の値を取得
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]

N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx.sort(key = itemgetter(2))
D = [int(sys.stdin.readline()) for _ in range(Q)] 

T = DammyMap(D, D)
ans = [-1]*Q

for s, t, x in stx:
    tl = T.less(s - x)
    tr = T.less(t - x)
    d = tr - tl
    for _ in range(d):
        i = T.get(tl + 1)
        T.add(i, -1)
        ans[T.comp[i]-1] = x
print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
from operator import itemgetter
class DammyMap:
    #1-indexed
    def __init__(self, A, B):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.size)
    
    def count(self, i):
        #i(Bの元)以下の個数を取得
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        #iをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        # v番目の値を取得
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx.sort(key = itemgetter(2))
D = [int(sys.stdin.readline()) for _ in range(Q)] 
_, comp = compress(D)

T = DammyMap(D, D)

ans = [-1]*Q

for s, t, x in stx:
    tl = T.less(s - x)
    tr = T.less(t - x)
    d = tr - tl
    for _ in range(d):
        i = T.get(tl + 1)
        T.add(i, -1)
        ans[comp[i]] = x
print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
from collections import Counter
from bisect import bisect as br, bisect_left as bl
from operator import itemgetter
class DammyMap:
    #1-indexed
    def __init__(self, A, B):
        #Aに初期状態の要素をすべて入れる,Bは値域のリスト
        self.X, self.comp = self.compress(B)
        self.size = len(self.X)
        self.tree = [0] * (self.size + 1)
        self.p = 2**(self.size.bit_length() - 1)
        self.dep = self.size.bit_length()
        
        CA = Counter(A)
        S = [0] + list(accumulate([CA[self.X[i]] for i in range(self.size)]))
        for i in range(1, 1+self.size):
            self.tree[i] = S[i] - S[i - (i&-i)]
        
    def compress(self, L):
        #座圧
        L2 = list(set(L))
        L2.sort()
        C = {v : k for k, v in enumerate(L2, 1)}
        # 1-indexed
        return L2, C
    
    def leng(self):
        #今入っている個数を取得
        return self.count(self.size)
    
    def count(self, i):
        #i(Bの元)以下の個数を取得
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def less(self, v):
        #v(Bの元である必要はない)未満の個数を取得
        i = bl(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def leq(self, v):
        #v(Bの元である必要はない)以下の個数を取得
        i = br(self.X, v)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        #iをx個入れる,負のxで取り出す,iの個数以上取り出すとエラーを出さずにバグる
        i = self.comp[i]
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        
        
    def get(self, v):
        # v番目の値を取得
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s]
            k //= 2
        return self.X[s]

def compress(L):
    #座圧
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx.sort(key = itemgetter(2))
D = [int(sys.stdin.readline()) for _ in range(Q)] 
_, comp = compress(D)

T = DammyMap(D, D)

ans = [-1]*Q

for s, t, x in stx:
    tl = T.less(s - x)
    tr = T.less(t - x)
    d = tr - tl
    for _ in range(d):
        i = T.get(tl + 1)
        T.add(i, -1)
        ans[comp[i]] = x
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from operator import itemgetter
import sys

input = sys.stdin.readline

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1] * Q
jump = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1] * Q
jump = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)

Submission status: Accepted

Solution code:
import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

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

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

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

Submission status: Accepted

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

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

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

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

event.sort()

closed = []
ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heapq.heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while closed and closed[0][1] <= d :
        heapq.heappop(closed)
    
    if closed :
        print(closed[0][0])
    else :
        print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ref: https://atcoder.jp/contests/abc128/submissions/5654623

import sys
from bisect import bisect_left

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

    closure.sort()

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

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

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

    return ans


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin



readl = stdin.readline

## input
N,Q = map(int, readl().rstrip().split())
STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
Dn = [None for _ in range(Q+1)]
for i in range(Q):
  Dn[i] = int(readl().rstrip())
Dn[Q] = 10**10
ans = [-1] * (Q+1)
skip = [-1] * (Q+1)

for s,t,x in sorted(STX,key=lambda x:x[2]):
  l = bisect_left(Dn,s-x)
  r = bisect_left(Dn,t-x)
  while l < r:
    if skip[l] < 0:
      ans[l] = x
      skip[l] = r
      l += 1
    else:
      l = skip[l]

for d in ans[:-1]:
  print(d)

Submission status: Accepted

Solution code:
from heapq import heappop as hpp, heappush as hp
import sys
N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
stx = [(s-x, t-x, x) for s, t, x in stx]
stx.sort(reverse = True)

D = [int(sys.stdin.readline()) for _ in range(Q)] 
H = []
ans = [None]*Q

for i, d in enumerate(D):
    while stx and stx[-1][0] <= d:
        hp(H, stx.pop()[1:][::-1])    
    while H and H[0][1] <= d:
        hpp(H)
    if not H:
        ans[i] = -1
    else:
        ans[i] = H[0][0]

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
n, Q = [int(x) for x in sys.stdin.readline().split()]
stx = [[int(x) for x in sys.stdin.readline().split()] for i in range(n)]
q = [int(sys.stdin.readline()) for i in range(Q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(Q)]
skip = [-1 for i in range(Q)]

for (s, t, x) in stx:
  begin = bisect_left(q, s-x)
  end = bisect_left(q, t-x)
  while begin<end:
    if skip[begin]==-1:
      ans[begin] = x
      skip[begin] = end
      begin += 1
    else:
      begin = skip[begin]
for e in ans:
  print(e)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    import heapq
    N, Q = MI()
    event = []
    for _ in range(N):
        s, t, x = MI()
        event.append((s - x-0.5, 1, x))
        event.append((t - x-0.5, -1, x))

    for _ in range(Q):
        d = I()
        event.append((d, 0))

    # クエリも含めてソート
    event.sort(key=lambda x: x[0])

    # 工事現場が一番近いところを探すのにO(N)かけると死ぬのでlogNで調べることができるように優先度付きキューも使う
    occur = set()
    occur_priority = []

    for e in event:
        # 工事開始
        if e[1] == 1:
            occur.add(e[2])
            heapq.heappush(occur_priority, e[2])

        # 工事終了 occurはsetなので2回先に追加されたあとに2回削除ということを考慮
        elif e[1] == -1:
            if e[2] in occur:
                occur.remove(e[2])
            # heap木の要素の削除は遅いので、クエリのときに消す

        # クエリ
        elif e[1] == 0:
            if occur:
                while 1:
                    if occur_priority[0] in occur:
                        min_occur = occur_priority[0]
                        break
                    else:
                        heapq.heappop(occur_priority)
                print(min_occur)
            else:
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    import heapq
    N, Q = MI()
    event = []
    for _ in range(N):
        s, t, x = MI()
        event.append((s - x-0.5, 1, x))
        event.append((t - x-0.5, -1, x))

    for _ in range(Q):
        d = I()
        event.append((d, 0))

    # クエリも含めてソート
    event.sort(key=lambda x: x[0])

    # 工事現場が一番近いところを探すのにO(N)かけると死ぬのでlogNで調べることができるように優先度付きキューも使う
    occur = set()
    occur_priority = []

    for e in event:
        # 工事開始
        if e[1] == 1:
            occur.add(e[2])
            heapq.heappush(occur_priority, e[2])

        # 工事終了
        elif e[1] == -1:
            if e[2] in occur:
                occur.remove(e[2])

        # クエリ
        elif e[1] == 0:
            if occur:
                while 1:
                    if occur_priority[0] in occur:
                        min_occur = occur_priority[0]
                        break
                    else:
                        heapq.heappop(occur_priority)
                print(min_occur)
            else:
                print(-1)


if __name__ == '__main__':
    main()