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
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  # 1-indexed
    def __init__(self,n):  # 1~nを要素として持ちうる。
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  # kを木に加える
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): # kを木から削除する
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  # 1~kの和
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  # k以上の最小要素
        x = self.sum(k-1)
        if x == self.sum(self.n):  # k以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k-1)なるpの右端 + 1が答え
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  # k以下の最大要素
        x = self.sum(k)
        if x == 0:  # k以下の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k)なるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  # k番目の要素出力
        if k > self.sum(self.n):  # k個以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = kなるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

block = []
free = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    block.append([s-x,x])
    free.append([t-x,x])

b,d = compress(X)
block = [(x[0],d[x[1]]) for x in block]
free = [(x[0],d[x[1]]) for x in free]
heapq.heapify(block)
heapq.heapify(free)

ans = []
avl = AVL_like_BIT(len(d))
for i in range(q):
    D = readint()
    while block and block[0][0]<=D:
        a = heapq.heappop(block)
        avl.add(a[1])
    while free and free[0][0]<=D:
        a = heapq.heappop(free)
        avl.delete(a[1])
    ans.append(avl.lower_bound(0))

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

block = []
free = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    block.append([s-x,x])
    free.append([t-x,x])

b,d = compress(X)
block = [(x[0],d[x[1]]) for x in block]
free = [(x[0],d[x[1]]) for x in free]
heapq.heapify(block)
heapq.heapify(free)

ans = []

stop = []
heapq.heapify(stop)
deleted = []
heapq.heapify(deleted)

for i in range(q):
    D = readint()
    while block:
        if block[0][0]<=D:
            a = heapq.heappop(block)
            heapq.heappush(stop,a[1])
        else:
            break
    while free:
        if free[0][0]<=D:
            a = heapq.heappop(free)
            heapq.heappush(deleted,a[1])
        else:
            break
    while deleted:
        if stop[0] == deleted[0]:
            heapq.heappop(stop)
            heapq.heappop(deleted)
        else:
            break
    if stop:
        ans.append(stop[0])
    else:
        ans.append(-1)

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  # 1-indexed
    def __init__(self,n):  # 1~nを要素として持ちうる。
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  # kを木に加える
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): # kを木から削除する
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  # 1~kの和
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  # k以上の最小要素
        x = self.sum(k-1)
        if x == self.sum(self.n):  # k以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k-1)なるpの右端 + 1が答え
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  # k以下の最大要素
        x = self.sum(k)
        if x == 0:  # k以下の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k)なるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  # k番目の要素出力
        if k > self.sum(self.n):  # k個以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = kなるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

block = []
free = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    block.append([s-x,x])
    free.append([t-x,x])

b,d = compress(X)
block = [(x[0],d[x[1]]) for x in block]
free = [(x[0],d[x[1]]) for x in free]
heapq.heapify(block)
heapq.heapify(free)

ans = []
avl = AVL_like_BIT(len(d))
for i in range(q):
    D = readint()
    while block:
        if block[0][0]<=D:
            a = heapq.heappop(block)
            avl.add(a[1])
        else:
            break
    while free:
        if free[0][0]<=D:
            a = heapq.heappop(free)
            avl.delete(a[1])
        else:
            break        
    ans.append(avl.lower_bound(0))

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Submission status: Accepted

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

def main():
    N,Q = map(int,input().split())
    event = []
    
    for _ in range(N):
        s,t,x = map(int,input().split())
        event.append((s-x,1,x))
        event.append((t-x,0,x))
        
    for i in range(Q):
        a = int(input())
        event.append((a,2,i))
    
    event.sort()
    ans = [-1]*Q
    use = set()
    stop = []
    
    for a,b,c in event:
        if b == 1:
            use.add(c)
            heapq.heappush(stop,c)
        elif b == 0:
            use.remove(c)
        else:
            while stop and stop[0] not in use:
                heapq.heappop(stop)
            ans[c] = -1 if len(stop) == 0 else stop[0]
    
    for num in ans:
        print(num)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x))
  task.append((s-x,1,x))

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

task.sort()

se = set()
se_hp = []
for a,b,c in task:
  if not b:
    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)
    answer[c] = se_hp[0] if se_hp else -1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


# 区間updateと要素クエリ
class SegmentTree(object):

    def __init__(self, A, e, fn):
        self.fn = fn
        self.length = 2 ** (len(A) - 1).bit_length()
        self.data = [e] * (self.length * 2)
        for i in range(len(A)):
            self.data[i + self.length - 1] = A[i]
        for i in reversed(range(self.length - 1)):
            self.data[i] = self.fn(self.data[2 * i + 1], self.data[2 * i + 2])

    # 区間[l, r)の値とxをfnで比較して更新する
    def update(self, l, r, x):  # O(logN)
        l += self.length
        r += self.length
        while l < r:
            if l & 1:
                self.data[l] = self.fn(self.data[l], x)
                l += 1
            if r & 1:
                self.data[r - 1] = self.fn(self.data[r - 1], x)
                r -= 1
            l //= 2
            r //= 2

    # i番目の要素の値を取得する
    def query(self, i):  # O(logN)
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.fn(ret, self.data[i])
        return ret

N, Q = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree([INF] * Q, INF, min)
for S, T, X in STX:
    # [S - X, T - X) に出発する人[l番目の人, r番目の人)が影響を受ける
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


# 区間updateと要素クエリ
class SegmentTree(object):

    def __init__(self, A, e, fn):
        self.fn = fn
        self.length = 1 << len(A).bit_length()
        self.data = [e] * (self.length * 2)
        for i in range(len(A)):
            self.data[i + self.length - 1] = A[i]
        for i in reversed(range(self.length - 1)):
            self.data[i] = self.fn(self.data[2 * i + 1], self.data[2 * i + 2])

    # 区間[l, r)の値とxをfnで比較して更新する
    def update(self, l, r, x):  # O(logN)
        l += self.length
        r += self.length
        while l < r:
            if l & 1:
                self.data[l] = self.fn(self.data[l], x)
                l += 1
            if r & 1:
                self.data[r - 1] = self.fn(self.data[r - 1], x)
                r -= 1
            l //= 2
            r //= 2

    # i番目の要素の値を取得する
    def query(self, i):  # O(logN)
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.fn(ret, self.data[i])
        return ret

N, Q = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree([INF] * Q, INF, min)
for S, T, X in STX:
    # [S - X, T - X) に出発する人[l番目の人, r番目の人)が影響を受ける
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


# 区間updateと要素クエリ
class SegmentTree(object):

    def __init__(self, n, e, fn):
        self.fn = fn
        self.length = 1 << n.bit_length()
        self.data = [e] * (self.length * 2)

    # 区間[l, r)の値とxをfnで比較して更新する
    def update(self, l, r, x):  # O(logN)
        l += self.length
        r += self.length
        while l < r:
            if l & 1:
                self.data[l] = self.fn(self.data[l], x)
                l += 1
            if r & 1:
                self.data[r - 1] = self.fn(self.data[r - 1], x)
                r -= 1
            l //= 2
            r //= 2

    # i番目の要素の値を取得する
    def query(self, i):  # O(logN)
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.fn(ret, self.data[i])
        return ret

N, Q = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree(Q, INF, min)
for S, T, X in STX:
    # [S - X, T - X) に出発する人[l番目の人, r番目の人)が影響を受ける
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


# 区間updateと要素クエリ
class SegmentTree(object):

    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)

    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret

N, Q = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree(Q, INF, min)
for S, T, X in STX:
    # [S - X, T - X) に出発する人(l番目の人からr番目の人まで)が影響を受ける
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

import sys
input = sys.stdin.buffer.readline


def main():

    n, q = map(int, input().split())
    stx = [map(int, input().split()) for _ in range(n)]
    ds = [int(input()) for _ in range(q)]
    INF = 10 ** 9 + 1
    CHECK = 2
    START = 1
    END = 0
    NULL = 0

    tfdi = []
    for i, (s, t, x) in enumerate(stx):
        t_start = max(0, s - x)
        t_end = max(0, t - x)

        tfdi.append((t_start, START, x, i))
        tfdi.append((t_end, END, x, i))

    for d in ds:
        tfdi.append((d, CHECK, NULL, NULL))
    tfdi.append((INF, START, INF, -1))
    tfdi.sort()

    hp = [(INF, -1)]
    ans = []
    passed = set()
    for t, f, d, i in tfdi:
        if f == CHECK:
            while hp[0][1] in passed:
                heappop(hp)
            if hp[0][0] == INF:
                tmp = -1
            else:
                tmp = hp[0][0]
            ans.append(tmp)

        elif f == START:
            heappush(hp, (d, i))
        else:
            passed.add(i)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
sys.setrecursionlimit(10 ** 7)
mod = 10**9 + 7

import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

N = q
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 10**9 + 1)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]



import bisect

for i, (x, start, last) in enumerate(stx):
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, (i, x))

for i in range(q):
    res = query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

Submission status: Accepted

Solution code:
# E - Roadwork
# https://atcoder.jp/contests/abc128/tasks/abc128_e

from heapq import heappop, heappush
from collections import defaultdict

n, q = map(int,input().split())
task = []
for _ in range(n): 
  s, t, x = map(int, input().split())
  task.append((t - x, 0, x)) 
  task.append((s - x, 1, x)) 

for i in range(q):
  d = int(input())
  task.append((d, 2, i)) 

answer = [-1] * q

task.sort()

se = set()
se_hp = []

for a, b, c in task:
  if b == 0:
    se.remove(c)
  elif b == 1:
    se.add(c)
    heappush(se_hp, c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,q = LI()
    stx = [LI() for _ in range(n)]
    da = [I() for _ in range(q)]

    q = []
    for s,t,x in stx:
        sx = s - x
        tx = t - x - 1
        heapq.heappush(q, (sx, x, tx))

    t = []
    cx = inf
    ctx = inf
    c = 0
    while len(q):
        sx, x, tx = heapq.heappop(q)
        # print("x", sx,x,tx)
        # print("q", q)
        # print("t", t)
        if sx > ctx:
            t.append((sx-1, cx))
            cx = x
            ctx = tx
        elif cx > x:
            if ctx > tx:
                heapq.heappush(q, (tx+1, cx, ctx))
            t.append((sx-1, cx))
            cx = x
            ctx = tx
        elif tx > ctx:
            heapq.heappush(q, (ctx+1, x, tx))

    t.append((inf, inf))
    # print("t", t)

    r = []
    for d in da:
        i = bisect.bisect_right(t, (d, -1))
        # print("d",d,i,t[i])
        u = t[i][1]
        if u == inf:
            r.append(-1)
        else:
            r.append(u)

    return JA(r, "\n")

print(main())

Submission status: Accepted

Solution code:
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()

    from heapq import heappush, heappop 

    running = [] # 止まりうる座標
    events = [] # 時刻順のイベント
    finished = set() # 工事が終了した座標

    n, q = map(int, input().split())
    for _ in range(n):
        s, t, x = map(int, input().split())
        events.append((s - x, x, 1)) # 追加イベント
        events.append((t - x, x, 0)) # 削除イベント
    for _ in range(q):
        d = int(input())
        events.append((d, 10**10, 2)) # 出発イベント,同じ時刻内で最後になるよう第二引数設定
    events.sort()
    for i in range(len(events)):
        temp = events[i]
        if temp[-1] == 1:
            heappush(running, temp[1])
            finished.discard(temp[1])
        elif temp[-1] == 0:
            finished.add(temp[1])
        else:
            flag = 1
            while running:
                p = heappop(running)
                if p not in finished:
                    flag = 0
                    heappush(running, p)
                    print(p)
                    break
            if flag:
                print(-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

def segfun(x, y):
    return min(x, y)
ide_ele = 10**9 + 1


class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)
 
    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret


n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
# stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

import bisect

seg = SegmentTree(q, ide_ele, segfun)

for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    seg.update(l, r, x)

for i, j in enumerate(d):
    res = seg.query(i)
    if res == ide_ele:
        print(-1)
    else:
        print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

def segfun(x, y):
    return min(x, y)
ide_ele = float("inf")


class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)
 
    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret


n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
# stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

import bisect

seg = SegmentTree(q, ide_ele, segfun)

for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    seg.update(l, r, x)

for i, j in enumerate(d):
    res = seg.query(i)
    if res == float("inf"):
        print(-1)
    else:
        print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()

    n, q = map(int, input().split())
    stx = []
    for _ in range(n):
        s, t, x = map(int, input().split())
        stx.append([x, s - x, t - x])
    stx.sort(reverse=True)
    d = [int(input()) for _ in range(q)]

    N = q
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)
    INF = (-1, 10**9 + 1)
    def update(l, r, v):
        L = l + N0; R = r + N0
        while L < R:
            if R & 1:
                R -= 1
                data[R-1] = v

            if L & 1:
                data[L-1] = v
                L += 1
            L >>= 1; R >>= 1
    def _query(k):
        k += N0-1
        s = INF
        while k >= 0:
            if data[k]:
                s = max(s, data[k])
            k = (k - 1) // 2
        return s
    def query(k):
        return _query(k)[1]



    import bisect

    for i, (x, start, last) in enumerate(stx):
        l = bisect.bisect_left(d, start)
        r = bisect.bisect_left(d, last)
        update(l, r, (i, x))

    for i in range(q):
        res = query(i)
        if res == 10**9 + 1:
            print(-1)
        else:
            print(res)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

N = q
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 10**9 + 1)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]



import bisect

for i, (x, start, last) in enumerate(stx):
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, (i, x))

for i in range(q):
    res = query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

N = q
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 10**9 + 1)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]



import bisect

for i, (x, start, last) in enumerate(stx):
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, (i, x))

for i, j in enumerate(d):
    res = query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)