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 = lambda : sys.stdin.readline().rstrip()

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, 10**9 + 1, lambda a, b : min(a, b))

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 == 10**9 + 1:
        print(-1)
    else:
        print(res)

Submission status: Accepted

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

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, 10**9 + 1, lambda a, b : min(a, b))

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 == 10**9 + 1:
        print(-1)
    else:
        print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline # 入出力高速化

def main():
    N, Q = map(int, input().split())
    tl = [] # イベントタイムライン
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    tl.sort()
    working = set() # 工事中
    wcur = 0 # 工事中の区域の数
    curmin = -1
    flag = False
    for t, c, x in tl:
        if c == 0: # erase
            wcur -= 1
            working.remove(x)
            if x <= curmin:
                curmin = x
                flag = True
        elif c == 1: # insert
            wcur += 1
            working.add(x)
            if curmin < 0 or curmin >= x:
                curmin = x
                flag = False
        else: # min
            if wcur == 0:
                curmin = -1
                flag = False
            elif flag:
                curmin = min(working)
                flag = False
            print(curmin)
    return
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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())
chk = []
for i in range(n):
  s,t,x = map(int,input().split())
  chk.append((s-x,t-x,x))
  
d = [int(input()) for i in range(q)]
seg = SegmentTree(q,10**9+1,lambda a, b: min(a,b))

for a,b,x in chk:
  L = bisect_left(d,a)
  R = bisect_left(d,b)
  seg.update(L,R,x)
  
for i in range(q):
  m = seg.query(i)
  if m == 10**9+1:
    print(-1)
  else:
    print(m)

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, n, ele, segfun):
        #####単位元######要設定0or1orinf
        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_add(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] += val
                l += 1
            if r & 1:
                self.data[r - 1] += val
                r -= 1
            l //= 2
            r //= 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())
chk = []
for i in range(n):
  s,t,x = map(int,input().split())
  chk.append((s-x,t-x,x))
d = [int(input()) for i in range(q)]
seg = SegmentTree(q,10**9+1,lambda a, b: min(a,b))

for a,b,x in chk:
  L = bisect_left(d,a)
  R = bisect_left(d,b)
  seg.update(L,R,x)
  
for i in range(q):
  m = seg.query(i)
  if m == 10**9+1:
    print(-1)
  else:
    print(m)

Submission status: Accepted

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

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        #ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            #ans.append(x)
            flag = 0
            break
    if flag:
        print(-1)

Submission status: Accepted

Solution code:
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
# a_iの現在の値を取得
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]

from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    stx = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
    l = [int(stdin.readline().rstrip()) for _ in range(q)]

    INF = (-1, 2**31-1)
    N = len(l)
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for i, (s, t, x) in enumerate(stx):
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, (i, x))

    for i in range(q):
        tmp = query(i)
        if tmp == INF[1]:
            print(-1)
        else:
            print(tmp)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_left 
from operator import itemgetter
def main():
    n, q = map(int, readline().split())
    STX = []
    for _ in range(n):
        s, t, x = map(int, readline().split())
        STX.append((s, t, x))
    D = []
    for _ in range(q):
        d = int(readline())
        D.append(d)

    STX.sort(key=itemgetter(2))

    ans = [-1 for _ in range(q)]
    skipTo = [-1 for _ in range(q)]
    for s, t, x in STX:
        #Dは狭義単調増加列で与えられている
        #s-x<=d<t-xとなるようなDの要素dが格納されている範囲のインデックスを求める
        #以下のようにすれば[left,right]のdがs-x<= d < t-xを満たす
        left = bisect_left(D, s-x)
        right = bisect_left(D, t-x)

        #xが小さいほど早い時刻で歩くのを止めることになる
        #よって、xの昇順に並んでいるので初めて[left, right)の範囲に入ったときだけansを更新するようにしたい
        #skiptoリストを用いて初めてでないときは飛ばすようにする
        while left < right: 
            if skipTo[left] == -1:
                #[left, right)は"このforループ"でansが決まる
                #よってleftが以前ansを決めたインデックスならright未満まではansが決まっているはずなのでrightまでとばす
                #そのためにrightを記録する
                skipTo[left] = right
                ans[left] = x
                left += 1
            else:
                #sikipTo[left]未満はansが決まっているので飛ばす
                left = skipTo[left] 
    for i in ans:
        print(i)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# E - Roadwork
from bisect import bisect_left
from operator import itemgetter


def main():
    N, Q, *STXD = map(int, open(0).read().split())
    STX, D = sorted(zip(*[iter(STXD[: 3 * N])] * 3), key=itemgetter(2)), STXD[3 * N :]
    ans = [-1] * Q
    road = [-1] * Q  # (road[i] = x) := if -1: open / else: closed until x
    for s, t, x in STX:
        l, r = bisect_left(D, s - x), bisect_left(D, t - x)
        while l < r:
            if road[l] == -1:
                ans[l] = x
                road[l] = r
                l += 1
            else:
                l = road[l]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - Roadwork
from bisect import bisect_left
from operator import itemgetter


def main():
    N, Q, *STXD = map(int, open(0).read().split())
    D = STXD[3 * N :]
    ans = [-1] * Q
    road = [-1] * Q  # (road[i] = x) := if -1: open / else: closed until x
    for s, t, x in sorted(zip(*[iter(STXD[: 3 * N])] * 3), key=itemgetter(2)):
        l, r = bisect_left(D, s - x), bisect_left(D, t - x)
        while l < r:
            if road[l] == -1:
                ans[l] = x
                road[l] = r
                l += 1
            else:
                l = road[l]
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline # 入出力高速化

def main():
    N, Q = map(int, input().split())
    tl = [] # イベントタイムライン
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    tl.sort()
    working = set() # 工事中
    wcur = 0 # 工事中の区域の数
    curmin = -1
    flag = False
    for t, c, x in tl:
        if c == 0: # erase
            wcur -= 1
            working.remove(x)
            if x <= curmin:
                curmin = x
                flag = True
        elif c == 1: # insert
            wcur += 1
            working.add(x)
            if curmin < 0 or curmin >= x:
                curmin = x
                flag = False
        else: # min
            if wcur == 0:
                curmin = -1
                flag = False
            elif flag:
                curmin = min(working)
                flag = False
            print(curmin)
    return
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    N, Q = map(int, input().split())
    tl = [] # イベントタイムライン
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    tl.sort()
    working = set() # 工事中
    wcur = 0 # 工事中の区域の数
    curmin = -1
    flag = False
    for t, c, x in tl:
        if c == 0: # erase
            wcur -= 1
            working.remove(x)
            if x <= curmin:
                curmin = x
                flag = True
        elif c == 1: # insert
            wcur += 1
            working.add(x)
            if curmin < 0 or curmin >= x:
                curmin = x
                flag = False
        else: # min
            if wcur == 0:
                curmin = -1
                flag = False
            elif flag:
                curmin = min(working)
                flag = False
            print(curmin)
    return
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    stx = []
    tmp = set([])

    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append((s,t,x))
        tmp.add(x-t)
        tmp.add(x-s)

    d = {}
    for i in range(q):
        di = -int(input())
        tmp.add(di)
        d[di] = i

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

    v2i = {}

    for i, v in enumerate(sorted(tmp)):
        v2i[v] = i

    l = [1] * (len(tmp) + 1)

    for di in d:
        l[v2i[di]] = di
            

    #####単位元######
    ide_ele_min = 1

    #num_min:n以上の最小の2のべき乗
    N = len(l)

    num_min =2**(N-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min

    def init_min(init_min_val):
        #set_val
        for i in range(N):
            seg_min[i+num_min-1]=init_min_val[i]    
        #built
        for i in range(num_min-2,-1,-1) :
            seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
    def update_min(k,x):
        k += num_min-1
        seg_min[k] = x
        while k:
            k = (k-1)//2
            seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
        
    def query_min(p,q):
        if q<=p:
            return ide_ele_min
        p += num_min-1
        q += num_min-2
        res=ide_ele_min
        while q-p>1:
            if p&1 == 0:
                res = min(res,seg_min[p])
            if q&1 == 1:
                res = min(res,seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,seg_min[p])
        else:
            res = min(min(res,seg_min[p]),seg_min[q])
        return res



    init_min(l)
    ans = [-1] * q

    for s, t, x in stx:
        l = v2i[x-t] + 1
        r = v2i[x-s] + 1
        v = query_min(l, r)
        while v != 1:
            i_d = d[v]
            i_sg = v2i[v]
            ans[i_d] = x
            update_min(i_sg, 1)
            v = query_min(l, r)

    for ansi in ans:
        print(ansi)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        return self.find(x) == self.find(y)
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [-1]*Q
    nxt = [i+1 for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: x[2])
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_left(D, R+1)
        p = L_idx
        while p < R_idx:
            if ans[p] == -1:
                ans[p] = X
                uf.union(L_idx, p)
                nxt[p] = R_idx
                p += 1
            else:
                par = uf.find(p)
                p = nxt[par]
                uf.union(L_idx, par)
                par = uf.find(par)
                if nxt[par] < R_idx:
                    nxt[par] = R_idx
                if nxt[par] < p:
                    nxt[par] = p
    for i in range(Q):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
data = []
n,q = map(int,input().split())
for i in range(n):
    s, t, x = map(int, input().split())
    data.append([s-x,t-x,x])
data.sort(key=lambda x:x[0])
d_index = 0
candidate_x = []
inf = float("inf")
data += [[inf,inf,inf]]
for i in range(q):
    d = int(input())
    while d >= data[d_index][0]:
        heappush(candidate_x, (data[d_index][2], data[d_index][1]))
        d_index += 1
    if len(candidate_x) == 0:
        print(-1)
    else:
        while candidate_x:
            x,finish_t = heappop(candidate_x)
            if finish_t > d:
                heappush(candidate_x, (x, finish_t))
                print(x)
                break
        else:
            print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 1<<31
from bisect import bisect_left

def main():
    N,Q = map(int,input().split())
    roadwork = [tuple(map(int,input().split())) for _ in range(N)]
    roadwork.sort(key = lambda x:x[2])
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    skip = [-1] * Q
    for s,t,x in roadwork:
        L = bisect_left(D,s - x)
        R = bisect_left(D,t - x)
        while L < R:
            if skip[L] == -1:
                ans[L] = x
                skip[L] = R
                L += 1
            else:
                L = skip[L]
    print('\n'.join(map(str,ans)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 1<<31
from heapq import heapify,heappop,heappush
from collections import defaultdict

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):
    d = int(input())
    event.append((d,1,i))

q = []
ans = [-1] * Q
event.sort()
push = defaultdict(int)
pop = defaultdict(int)
for i in range(2*N + Q):
    t,typ,x = event[i]
    if typ == -1:
        heappush(q,x)
        push[x] += 1
    elif typ == 0:
        pop[x] += 1
    else:
        p = -1
        if q:
            p = q[0]
        while p != -1 and push[p] - pop[p] == 0:
            heappop(q)
            if q:
                p = q[0]
            else:
                p = -1
                break
        ans[x] = p
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = (1<<31)
from bisect import bisect_left

class LazySegmentTree():

    def __init__(self,Q):
        self.N = Q
        self.tree = [INF]*(2*self.N)
        self.lazy = [INF]*(2*self.N)
   
    def _evaluate(self,K):#Kの上の遅延配列を評価する
        H = K.bit_length() - 1
        for i in range(H,0,-1):
            h = K >> i
            if self.lazy[h] == INF:
                continue
            self.tree[h] = min(self.tree[h],self.lazy[h])
            self.lazy[h << 1] = min(self.lazy[h << 1],self.lazy[h])
            self.lazy[h << 1|1] = min(self.lazy[h << 1|1],self.lazy[h])
            self.lazy[h] = INF
    
    def _caluculate(self,K):#Kより上を計算する
        while K > 1:
            K >>= 1
            self.tree[K] = min(self.tree[K],self.tree[K<<1],self.lazy[K<<1],self.tree[K<<1|1],self.lazy[K<<1|1])

    def range_update(self,L,R,M):#[L,R)にMを作用
        L += self.N
        R += self.N
        L0 = L//(L & -L)
        R0 = R//(R & -R) - 1
        #self._evaluate(L0)
        #self._evaluate(R0)
        while L < R:
            if L&1:
                self.lazy[L] = min(self.lazy[L],M)
                L += 1
            if R&1:
                R -= 1
                self.lazy[R] = min(self.lazy[R],M)
            L >>= 1
            R >>= 1
        #print("L0 R0 {} {}\n".format(L0,R0))
        self._caluculate(L0)
        self._caluculate(R0)
    
    def range_query(self,L,R):#[L,R)を計算する
        L += self.N
        R += self.N
        L0 = L//(L & -L)
        R0 = R//(R & -R) - 1
        self._evaluate(L0)
        self._evaluate(R0)
        v = INF
        while L < R:
            if L&1:
                v = min(v,self.tree[L],self.lazy[L])
                L += 1
            if R&1:
                R -= 1
                v = min(self.tree[R],self.lazy[R],v)
            L >>= 1
            R >>= 1
        return v
    '''
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))
    '''
    def debug(self):
        print(self.lazy)
        print(self.tree)
    
    def __str__(self):
        for i in range(self.N):
            self.tree[i] = min(self.tree[i],self.lazy[i])
            self.lazy[i << 1] = min(self.lazy[i << 1],self.lazy[i])
            self.lazy[i << 1|1] = min(self.lazy[i << 1|1],self.lazy[i])
            self.lazy[i] = INF
        for i in range(self.N,self.N*2):
            self.tree[i] = min(self.tree[i],self.lazy[i])
        return '\n'.join(map(str,[k if k < INF else -1 for k in self.tree[self.N:]]))


N,Q = map(int,input().split())
roadwork = [tuple(map(int,input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
st = LazySegmentTree(Q)

for s,t,x in roadwork:
    l = bisect_left(D,s - x)
    r = bisect_left(D,t - x)
    st.range_update(l,r,x)
print(str(st))

Submission status: Accepted

Solution code:
import bisect
N,Q=map(int,input().split())
road=[]
pos=[]
for _ in range(N):
    s,t,x=map(int,input().split())
    road.append((s-x,t-x,x))
for _ in range(Q):
    pos.append(int(input()))
road.sort(key=lambda x:x[2])
ans=[-1]*Q
ischecked=[-1]*Q
for s,t,x in road:
    l=bisect.bisect_left(pos,s)
    r=bisect.bisect_left(pos,t)
    while l<r:
        if ischecked[l]==-1:
            ischecked[l]=r
            ans[l]=x
            l+=1
        else:
            l=ischecked[l]
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def YesNo(x):print("Yes")if x==True else print("No")
n,q=NM()
l=[]
for i in range(n):
    s,t,x=NM()
    l.append((s-x,t-x,x))
l.sort()
INF=float("inf")
l+=[(INF,INF,INF)]
d=LN(q)
q=[]
from heapq import heappush,heappop
j=0
for i in d:
    while l[j][0]<=i:
        s,t,x=l[j]
        heappush(q,(x,t))
        j+=1
    if len(q)==0:
        print(-1)
    else:
        while q:
            x,t=heappop(q)
            if t>i:
                heappush(q,(x,t))
                print(x)
                break
        else:
            print(-1)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def main():
    ConstNum,PersonNum=map(int,input().split())

    S=[]
    T=[]
    X=[]
    for i in range(ConstNum):
        s,t,x=map(int,input().split())
        S.append(s)
        T.append(t)
        X.append(x)

    DepartureTime=[]
    for i in range(PersonNum):
        d=int(input())
        DepartureTime.append(d)

    XST=zip(X,S,T)
    XST=sorted(XST)

    res=[-1]*PersonNum
    stop=[-1]*PersonNum

    for x,s,t in XST:
        left_value=s-x
        right_value=t-x

        left_index=bisect_left(DepartureTime,left_value)
        right_index=bisect_left(DepartureTime,right_value)

        while left_index<right_index:
            if stop[left_index]==-1:
                res[left_index]=x
                stop[left_index]=right_index
                left_index+=1
            else:
                left_index=stop[left_index]

    for i in range(PersonNum):
        print(res[i])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

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

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

for i in range(n):
    s,t,x=stx[i]
    left=bisect.bisect_left(d, s-x)
    right=bisect.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
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,q = map(int, input().split())
    l = []
    for _ in range(n):
        s,t,x = map(int, input().split())
        l.append((s,t,x))
    l.sort(key=lambda a: a[2])
    start = [int(input()) for _ in range(q)]

    skip = [-1]*q
    res = [-1]*q

    for s,t,x in l:
        left = bisect_left(start, s-x)
        right = bisect_left(start, t-x)
        while left < right:
            if skip[left] == -1:
                res[left] = x
                skip[left] = right
                left += 1
            else:
                left = skip[left]
    
    for i in res:
        print(i)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

class SegmentTree():
    def __init__(self,size,func,default):
        self.leaf=2**(size-1).bit_length()
        self.data=[default]*(2*self.leaf-1)
        self.f=func; self.d=default
    def rangeupdate(self,l,r,x):
        l+=self.leaf-1; r+=self.leaf-1
        while l<r:
            if not l&1:
                self.data[l]=self.f(self.data[l],x)
                l+=1
            if not r&1:
                r-=1
                self.data[r]=self.f(self.data[r],x)
            l>>=1; r>>=1
    def getvalue(self,i):
        k=i+self.leaf-1
        ret=self.d
        while k>=0:
            ret=self.f(ret,self.data[k])
            k=(k-1)>>1
        return ret

#最大値            
def segfunc(x,y):
    return max(x,y)

#最小値
def segfunc2(x,y):
    return min(x,y)
#和
def segfunc3(x,y):
    return x | y


def main():
    N, Q = map(int, input().split())
    construction = []
    for _ in range(N):
        S, T, X = map(int, input().split())
        construction.append([S,T,X])

    D = [int(input()) for _ in range(Q)]
    seg = SegmentTree(Q,segfunc2,float('inf'))

    for i in range(N):
        S, T, X = construction[i]
        l = bisect_left(D, S - X)
        r = bisect_left(D, T - X)
        seg.rangeupdate(l, r, X)
    
    for q in range(Q):
        ans = seg.getvalue(q)
        if ans == float('inf'):
            print(-1)
        else:
            print(ans)

if __name__ == "__main__":
    main()