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:
import sys
input = sys.stdin.buffer.readline
n,q=map(int,input().split())
import heapq
S=[]
D=dict()
for i in range(n):
  s,t,x=map(int,input().split())
  S.append((1,x,max(0,s-x)))
  S.append((-1,x,max(0,t-x)))
  D[x]=False
S.sort(key=lambda x:x[2])
X=[]
cur=0
for i in range(q):
  d=int(input())
  while cur<2*n:
    a,b,c=S[cur]
    if c>d:
      break
    else:
      cur+=1
      if a==1:
        heapq.heappush(X,b)
        D[b]=True
      else:
        D[b]=False
  while X:
    ans=heapq.heappop(X)
    if D[ans]:
      print(ans)
      heapq.heappush(X,ans)
      break
  if not X:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
import heapq
S=[]
D=dict()
for i in range(n):
  s,t,x=map(int,input().split())
  S.append((1,x,max(0,s-x)))
  S.append((-1,x,max(0,t-x)))
  D[x]=False
S.sort(key=lambda x:x[2])
X=[]
cur=0
for i in range(q):
  d=int(input())
  while cur<2*n:
    a,b,c=S[cur]
    if c>d:
      break
    else:
      cur+=1
      if a==1:
        heapq.heappush(X,b)
        D[b]=True
      else:
        D[b]=False
  while X:
    ans=heapq.heappop(X)
    if D[ans]:
      print(ans)
      heapq.heappush(X,ans)
      break
  if not X:
    print(-1)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/submissions/7097699
import sys
input = sys.stdin.readline

from bisect import bisect_left

n,q = map(int, input().split())
road = [list(map(int, input().split())) for i in range(n)]
road.sort(key=lambda x: x[2])
start = [int(input()) for i in range(q)]

skip = [-1]*q
ans = [-1]*q
for s,t,x in road:
    left = bisect_left(start, s-x)
    right = bisect_left(start, t-x)
    # [left, right)をxで埋める
    # すでに存在するところ(skipがあるところ)は飛ばす
    while left < right:
        if skip[left] == -1:
            ans[left] = x
            skip[left] = right
            left += 1
        else:
            left = skip[left]
print(*ans, sep="\n")

Submission status: Accepted

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

class RangeUpdateQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.INF = float("inf")
        self.data = [self.INF]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] = v
            if l&1:
                self.data[l-1] = v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = self.INF
        while i+1:
            if self.data[i] < res:
                res = self.data[i]
            i = ~-i//2
        return res

n,q = map(int, input().split())
start = [None]*q
se = set()

road = []
for i in range(n):
    s,t,x = map(int, input().split())
    road.append([x, x-t, x-s])
for i in range(q):
    d = int(input())
    start[i] = -d

start = start[::-1]

RUQ = RangeUpdateQuery(q)
road.sort(reverse=True)
from bisect import bisect_left,bisect_right
for i, (x, s, t) in enumerate(road):
    l = bisect_right(start, s)
    r = bisect_right(start, t)
    #print(x, (s,t), l, r)
    RUQ.update(l, r, x)

ans = []
for i in range(q):
    x = RUQ.query(i)
    if x == float("inf"):
        x = -1
    ans.append(x)
ans = ans[::-1]
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

from operator import itemgetter
from bisect import bisect_left

class Range_SegmentTree:
    def __init__(self,N):
        self.N0 = 2**(N-1).bit_length()
        self.tree = [None]*(2*self.N0)    
        self.INF = (-1, 2**31-1)

    #区間[l,r]の値をvに書き換える
    #vは(t,value)という値にする (新しい値ほどtは大きくなる)
    def update(self,l,r,v):
        L = l + self.N0; R = r + self.N0 + 1
        while L < R:
            if R & 1:
                R -= 1
                self.tree[R-1] = v
            if L & 1:
                self.tree[L-1] = v
                L += 1
            L >>= 1; R >>= 1

    #a[k]の現在の値を更新時刻と共に取得
    def _query(self,k):
        k += self.N0-1
        s = self.INF
        while k >= 0:
            if self.tree[k]:
                s = max(s, self.tree[k])
            k = (k - 1) // 2
        return s

    #a[k]を返す
    def query(self,k):
        return self._query(k)[1]
      
N,Q = II()
a = []
for _ in range(N):
    s,t,x = II()
    a.append((x, s-x-0.5, t-x-0.5))
D = Line(Q,1)
 
a.sort(key=itemgetter(0),reverse=True)
 
seg = Range_SegmentTree(Q)
for i,b in enumerate(a):
    l = bisect_left(D,b[1])
    r = bisect_left(D,b[2])
    seg.update(l,r-1,(i,b[0]))
    
for i in range(Q):
    x = seg.query(i)
    if x == 2**31-1:
        print(-1)
    else:
        print(x)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))

#################

from operator import itemgetter
from bisect import bisect_left

N,Q = II()
a = []
for _ in range(N):
    s,t,x = II()
    a.append((x, s-x-0.5, t-x-0.5))
a.sort(key=itemgetter(0))
D = Line(Q,1)

ans = [-1]*(Q+1)
right = [0]*Q
for a0 in a:
    l = bisect_left(D,a0[1])
    r = bisect_left(D,a0[2])
    while l<r:
        while ans[l]!=-1:
            l = right[l]
            if l==N:
                break
        if l>=r:
            break
        ans[l] = a0[0]
        right[l] = r
        l += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
INF = float('inf')

class SegmentTree:

    def __init__(self, N):
        self.N = 1<<(N-1).bit_length()
        self.data = [None] * (2*self.N)

    def Update(self, l, r, t, v):
        L, R, val = l+self.N, r+self.N, (t, v)
        while L < R:
            if R & 1:
                R -= 1
                self.data[R-1] = val
            if L & 1:
                self.data[L-1] = val
                L += 1
            L >>= 1
            R >>= 1

    def getValue(self, x):
        x += self.N-1
        ret = (-1, INF)
        while x >= 0:
            if self.data[x]:
                ret = max(ret, self.data[x])
            x = (x-1)//2
        return ret[1]

N, Q = map(int, input().split())
stx = [[int(x) for x in input().split()] for i in range(N)]
stx.sort(key = lambda v : -v[2])
D = [(int(input()), i) for i in range(Q)]
D.sort(key = lambda v : v[0])
d, p = [d for d, p in D], [p for d, p in D]
seg = SegmentTree(Q)
for i, (s, t, x) in enumerate(stx):
    l = bisect_left(d, s-x)
    r = bisect_left(d, t-x)
    seg.Update(l, r, i, x)
ans = [None] * Q
for i in range(Q):
    tmp = seg.getValue(i)
    if tmp == INF:
        tmp = -1
    ans[p[i]] = tmp
print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
INF = 10 ** 18

from collections.abc import Sequence, Set
from bisect import bisect_left
from itertools import chain

from heapq import heappush, heappop

class HeapSet():
    # 最小値を O(log n) で取り出せる set. 中身としては、入っているものを set で管理し、順番を heapq で管理しているだけ。
    def __init__(self):
        self._set = set()
        self._list = list()

    def add(self, a):
        if a in self._set:
            return
        else:
            self._set.add(a)
            heappush(self._list, a)

    def remove(self, a):
        if a not in self._set:
            raise ValueError
        else:
            self._set.remove(a)

    def peek(self):
        if not self._set:
            self._list = list()
            raise IndexError
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        return a

    def pop(self):
        a = self.peek()
        self._set.remove(a)
        heappop(self._list)
        return a


    def get_set(self): return self._set
    def get_heapq(self): return self._list
    def get_list(self): return self._list
    def __bool__(self): return True if self._set else False
    def __contains__(self, a): return a in self._set
    def __len__(self): return len(self._set)
    def __repr__(self): return "HeapSet(" + (repr(self._set) if self._set else '') + ")"





def main(): 
    N, Q = LI()
    events = []
    for _ in range(N):
        stx = LI()
        # events.append((s - x, x, True))  # S-X, X, add_flag
        # events.append((t - x, x, False))  # T-X, X, add_flag
        events.append((stx[0] - stx[2], stx[2], True))  # S-X, X, add_flag
        events.append((stx[1] - stx[2], stx[2], False))  # T-X, X, add_flag
    for _ in range(Q):
        events.append((II(), INF, -1))
 
    # events.sort(key=lambda x:x[0])  # O(N log N), stable
    events.sort()  # O(N log N), stable, False (==0) < True (==1)
 
    from array import array
    ans = array('i')
    # m = SortedList()
    m = HeapSet()
    # for time, x, add_flag in events:
    change_flag = True
    min_ = INF
    for txa in events:
        if txa[2] == -1:
            if not m:
                ans.append(-1)
                # ans += '-1\n'
            else:
                if change_flag:
                    min_ = m.peek()
                    change_flag = False
                ans.append(min_)
                # ans += str(m[0])+'\n'
        elif txa[2]:
            m.add(txa[1])
            if txa[1] < min_:
                min_ = txa[1]
                change_flag = False
        else:
            m.remove(txa[1])
            if txa[1] == min_ and m:
                min_ = m.peek()
                change_flag = False
            elif not m:
                min_ = INF
                change_flag = False
 
    # for i in ans: print(i)
    # print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans.tolist())))


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
INF = 10 ** 18

from collections.abc import Sequence, Set
from bisect import bisect_left
from itertools import chain

from heapq import heappush, heappop

class HeapSet():
    # 最小値を O(log n) で取り出せる set. 中身としては、入っているものを set で管理し、順番を heapq で管理しているだけ。
    def __init__(self):
        self._set = set()
        self._list = list()

    def add(self, a):
        if a in self._set:
            return
        else:
            self._set.add(a)
            heappush(self._list, a)

    def remove(self, a):
        if a not in self._set:
            raise ValueError
        else:
            self._set.remove(a)

    def pop(self):
        if not self._set:
            self._list = list()
            raise IndexError
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        self._set.remove(a)
        return a

    def peek(self):
        if not self._set:
            self._list = list()
            raise IndexError
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        return a

    def get_set(self): return self._set
    def get_heapq(self): return self._list
    def get_list(self): return self._list
    def __bool__(self): return True if self._set else False
    def __contains__(self, a): return a in self._set
    def __len__(self): return len(self._set)
    def __repr__(self):
        return "HeapSet(" + (repr(self._set) if self._set else '') + ")"





def main(): 
    N, Q = LI()
    events = []
    for _ in range(N):
        stx = LI()
        # events.append((s - x, x, True))  # S-X, X, add_flag
        # events.append((t - x, x, False))  # T-X, X, add_flag
        events.append((stx[0] - stx[2], stx[2], True))  # S-X, X, add_flag
        events.append((stx[1] - stx[2], stx[2], False))  # T-X, X, add_flag
    for _ in range(Q):
        events.append((II(), INF, -1))
 
    # events.sort(key=lambda x:x[0])  # O(N log N), stable
    events.sort()  # O(N log N), stable, False (==0) < True (==1)
 
    from array import array
    ans = array('i')
    # m = SortedList()
    m = HeapSet()
    # for time, x, add_flag in events:
    change_flag = True
    min_ = INF
    for txa in events:
        if txa[2] == -1:
            if not m:
                ans.append(-1)
                # ans += '-1\n'
            else:
                if change_flag:
                    min_ = m.peek()
                    change_flag = False
                ans.append(min_)
                # ans += str(m[0])+'\n'
        elif txa[2]:
            m.add(txa[1])
            if txa[1] < min_:
                min_ = txa[1]
                change_flag = False
        else:
            m.remove(txa[1])
            if txa[1] == min_ and m:
                min_ = m.peek()
                change_flag = False
            elif not m:
                min_ = INF
                change_flag = False
 
    # for i in ans: print(i)
    # print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans.tolist())))

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
INF = 10 ** 18

from collections.abc import Sequence, Set
from bisect import bisect_left
from itertools import chain

from heapq import heappush, heappop

class HeapqSet():
    def __init__(self):
        self._set = set()
        self._list = list()

    def add(self, a):
        if a in self._set:
            return
        else:
            self._set.add(a)
            heappush(self._list, a)

    def remove(self, a):
        if a not in self._set:
            raise ValueError
        else:
            self._set.remove(a)

    def pop_min(self):
        if not self._set:
            self._list = list()
            return None
        while True:
            a = heappop(self._list)
            if a not in self._set:
                continue
            else:
                self._set.remove(a)
                break
        return a

    def peek_min(self):
        if not self._set:
            self._list = list()
            return None
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        return a

    def is_empty(self):
        return not self._set

    def __bool__(self):
        return True if self._set else False





def main(): 
    N, Q = LI()
    events = []
    for _ in range(N):
        stx = LI()
        # events.append((s - x, x, True))  # S-X, X, add_flag
        # events.append((t - x, x, False))  # T-X, X, add_flag
        events.append((stx[0] - stx[2], stx[2], True))  # S-X, X, add_flag
        events.append((stx[1] - stx[2], stx[2], False))  # T-X, X, add_flag
    for _ in range(Q):
        events.append((II(), INF, -1))
 
    # events.sort(key=lambda x:x[0])  # O(N log N), stable
    events.sort()  # O(N log N), stable, False (==0) < True (==1)
 
    from array import array
    ans = array('i')
    # m = SortedList()
    m = HeapqSet()
    # for time, x, add_flag in events:
    change_flag = True
    min_ = INF
    for txa in events:
        if txa[2] == -1:
            if not m:
                ans.append(-1)
                # ans += '-1\n'
            else:
                if change_flag:
                    min_ = m.peek_min()
                    change_flag = False
                ans.append(min_)
                # ans += str(m[0])+'\n'
        elif txa[2]:
            m.add(txa[1])
            if txa[1] < min_:
                min_ = txa[1]
                change_flag = False
        else:
            m.remove(txa[1])
            if txa[1] == min_ and m:
                min_ = m.peek_min()
                change_flag = False
            elif not m:
                min_ = INF
                change_flag = False
 
    # for i in ans: print(i)
    # print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans.tolist())))



main()

Submission status: Accepted

Solution code:
#48 ABC128E
#イベントソート   
import sys
input = sys.stdin.readline

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

stx=sorted(stx,key=lambda x:x[2])

ans=[-1 for _ in range(q)]
skip=[-1 for _ in range(q)]

from bisect import bisect_left

for s,t,x in stx:
	left=bisect_left(d,s-x)
	right=bisect_left(d,t-x)
	while left<right:
		if skip[left]==-1:
			ans[left]=x
			skip[left]=right
			left+=1
		else:
			left=skip[left]
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left

    N, Q = map(int, input().split())
    c = []
    c_append = c.append
    for _ in range(N):
        s, t, x = map(int, input().split())
        c_append((x, s, t))
    c.sort()

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

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

    for x, s, t in c:
        left = bisect_left(D, s - x)
        right = bisect_left(D, t - x)
        while left < right:
            if skip[left] == -1:
                ans[left] = x
                skip[left] = right
                left += 1
            else:
                left = skip[left]

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    from heapq import heappop, heappush
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    used = defaultdict(int)
    tank = []
    
    p = []
    p_append = p.append
    for i in range(N):
        s, t, x = map(int, input().split())
        p_append((s - x, x))
        p_append((t - x, -x))
    p.sort()

    cnt = 0
    for i in range(Q):
        d = int(input())
        while cnt <= len(p) - 1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w >= 0:
                used[w] += 1
                heappush(tank, w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print (-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print (kouho)
                break
            else:
                heappop(tank)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from heapq import heappop, heappush
from collections import defaultdict

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

lst = []
l_append = lst.append
for i in range(N):
    s, t, x = map(int, input().split())
    l_append((t - x, 0, x)) #xで止まらなくなる
    l_append((s - x, 1, x)) #xで止まる

for i in range(Q):
    l_append((int(input()), 2, i))

lst.sort()
ans = [-1] * Q

#引っかかっている場所の管理
se = set()
se_hp = [] #heapで最小値を先頭に保つ

#小さい時刻から順に見ていく
# s_remove = se.remove
# s_add = se.add
for a, b, c in lst:
    if b == 0:
        se.remove(c)
    elif b == 1:
        se.add(c)
        heappush(se_hp, c)
    else:
        while se_hp and se_hp[0] not in se:
            heappop(se_hp)
        ans[c] = se_hp[0] if se_hp else -1

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

Submission status: Accepted

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

from heapq import heappop, heappush
from collections import defaultdict

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

lst = []
l_append = lst.append
for i in range(N):
    s, t, x = map(int, input().split())
    l_append((t - x, 0, x)) #xで止まらなくなる
    l_append((s - x, 1, x)) #xで止まる

for i in range(Q):
    l_append((int(input()), 2, i))

lst.sort()
ans = [-1] * Q

#引っかかっている場所の管理
se = set()
se_hp = [] #heapで最小値を先頭に保つ

#小さい時刻から順に見ていく
s_remove = se.remove
s_add = se.add
for a, b, c in lst:
    if b == 0:
        s_remove(c)
    elif b == 1:
        s_add(c)
        heappush(se_hp, c)
    else:
        while se_hp and se_hp[0] not in se:
            heappop(se_hp)
        ans[c] = se_hp[0] if se_hp else -1

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

Submission status: Accepted

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

from heapq import heappop, heappush
from collections import defaultdict

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

lst = []
for i in range(N):
    s, t, x = map(int, input().split())
    lst.append((t - x, 0, x)) #xで止まらなくなる
    lst.append((s - x, 1, x)) #xで止まる

for i in range(Q):
    lst.append((int(input()), 2, i))

lst.sort()
ans = [-1] * Q

#引っかかっている場所の管理
se = set()
se_hp = [] #heapで最小値を先頭に保つ

#小さい時刻から順に見ていく
for a, b, c in lst:
    if b == 0:
        se.remove(c)
    elif b == 1:
        se.add(c)
        heappush(se_hp, c)
    else:
        while se_hp and se_hp[0] not in se:
            heappop(se_hp)
        ans[c] = se_hp[0] if se_hp else -1

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

N, Q = map(int, input().split())
R = [tuple(map(int, input().split())) for i in range(N)]
R.sort(key=lambda r: r[2])
q = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * (Q + 1)

for s, t, x in R:
    l = bisect_left(q, s - x)
    r = bisect_left(q, t - x)
    while l < r:
        if skip[l] == -1:
            skip[l] = r
            ans[l] = x
            l += 1
        else:
            l = skip[l]
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def main():
    kouji_num, person_num = map(int, input().split())
    koji_data = [list(map(int, input().split())) for i in range(kouji_num)]
    person_data = [int(input()) for i in range(person_num)]

    event_list = [0 for i in range(kouji_num * 2)]
    now_kouji = set()

    for i in range(kouji_num):
        start, fin, position = koji_data[i]
        event_list[2 * i] = (start - position - 0.25, 1, position)
        event_list[2 * i + 1] = (fin - position - 0.75, 0, position)
    event_list.sort(key=lambda x: x[0])

    ans = 10 ** 9 + 1
    now_ind = 0
    for i in range(person_num):
        person_start = person_data[i]
        while now_ind < kouji_num * 2:
            time_data, flg, position = event_list[now_ind]
            if time_data > person_start:
                break

            if flg:
                now_kouji.add(position)
                ans = min(ans, position)
            else:
                now_kouji.remove(position)
                if len(now_kouji) == 0:
                    ans = 10 ** 9 + 1
                elif ans == position:
                    ans = min(now_kouji)

            now_ind += 1
        if ans == 10 ** 9 + 1:
            print(-1)
        else:
            print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

def bs(d, x):
  l, r = 0, len(d)
  while l < r:
    mid = (l + r) // 2
    if d[mid] < x:
      l = mid + 1
    else:
      r = mid
  return l


def main():
  n, q = map(int, input().split())
  stx = [tuple(map(int, input().split())) for _ in range(n)]
  stx = list(sorted(stx, key=lambda x: x[2]))
  dlist = [int(input()) for _ in range(q)]
  ans = [-1 for _ in range(q)]
  skip = [-1 for _ in range(q)]
  for s, t, x in stx:
    l = bs(dlist, s-x)
    r = bs(dlist, t-x)
    while l < r:
      if skip[l] == -1:
        ans[l] = x
        skip[l] = r
        l += 1
      else:
        l = skip[l]
  print(*ans, sep='\n')


if __name__ == '__main__':
  main()

Submission status: Accepted

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

S = [None] * N
T = [None] * N
X = [None] * N
for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, key=lambda x: x[0])
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * Q
skip = [-1] * Q

import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
            i += 1
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def solve(n, q, s, t, x, d):
    v = sorted(list(zip(s, t, x)), key=lambda _:_[2])
    res = [-1] * q
    jump = [-1] * q
    for s, t, x in v:
        l = bisect_left(d, s - x)
        r = bisect_left(d, t - x)
        while l < r:
            s = jump[l]
            if s == -1:
                res[l] = x
                jump[l] = r
                l += 1
            else:
                l = s
    return res

n, q = map(int, input().split())
s = [-1] * n
t = [-1] * n
x = [-1] * n
for i in range(n):
    s[i], t[i], x[i] = map(int, input().split())
d = [int(input()) for i in range(q)]

print(*solve(n, q, s, t, x , d), sep="\n")

Submission status: Accepted

Solution code:
import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1 for _ in range(Q)]
queries =[]
jump = ans[::]



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# 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,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


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





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:

             lind = jump[lind]

for i  in ans:
    print(i)

Submission status: Accepted

Solution code:
import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1 for _ in range(Q)]
queries =[]
jump = ans[::]



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# 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,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


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





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)

Submission status: Accepted

Solution code:
import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# 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,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


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





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)