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 math
import numpy as np
import decimal
import collections
import itertools
import sys
import random
#Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#Prime-Factorize
def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res
#nCr
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
#拡張Euclidの互除法
def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y, x - a // b * y
    return x, y, g
#BIT
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res
#Associative Array
class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)
#Floor Sum
def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res
#Z-Algorithm
def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(self.s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and self.s[i - j] == self.s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k
#mod-sqrt
def mod_sqrt(a, p):
    if a == 0:
        return 0
    if p == 2:
        return 1
    k = (p - 1) // 2
    if pow(a, k, p) != 1:
        return -1
    while True:
        n = random.randint(2, p - 1)
        r = (n ** 2 - a) % p
        if r == 0:
            return n
        if pow(r, k, p) == p - 1:
            break
    k += 1
    w, x, y, z = n, 1, 1, 0
    while k:
        if k % 2:
            y, z = w * y + r * x * z, x * y + w * z
        w, x = w * w + r * x * x, 2 * w * x
        w %= p
        x %= p
        y %= p
        z %= p
        k >>= 1
    return y
import bisect
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 for i in range(q)]
lis = [-1 for i in range(q)]
for s, t, x in stx:
    l = bisect.bisect_left(d, s - x)
    r = bisect.bisect_left(d, t - x)
    while l < r:
        if lis[l] == -1:
            ans[l] = x
            lis[l] = r
            l += 1
        else:
            l = lis[l]
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18 if not DBG else 99999
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)


# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #

n,q = inm()
xs = set([])
stx = []
for i in range(n):
    s,t,x = inm()
    xs.add(x)
    xs.add(s-x)
    xs.add(t-x)
    stx.append((s-x,t-x,x))
stx.sort()

di = []
ans = [-1]*q
for i in range(q):
    d = inn()
    xs.add(d)
    di.append(d)

x2i = {}
i2x = list(xs)
m = len(xs)
i2x.sort()
for i,x in enumerate(i2x):
    x2i[x] = i

stx2 = []
for i in range(n):
    s,t,x = stx[i]
    stx2.append((x2i[s],x2i[t],x2i[x]))
d2 = [x2i[d] for d in di]

sgt = Segtree(m,BIG,lambda x,y: min(x,y))
top = 0
for j in range(q):
    d = d2[j]
    while top<n:
        s,t,x = stx2[top]
        if s>d:
            break
        if x<sgt.get(t-1):
            sgt.set(t-1,x)
        top += 1
    x = sgt.query(d,m)
    if x==BIG:
        print(-1)
    else:
        print(i2x[x])

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, Q = LI()
    sections = []
    D = []

    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        sections.append((s, t, x))

    for _ in range(Q):
        D.append(I())
    sections = sorted(sections, key=lambda x: (x[-1], x[-2]))

    section_end_ix = collections.defaultdict(list)

    filled = [-1] * Q
    for sec in sections:
        l = bisect.bisect_left(D, sec[0])
        r = bisect.bisect_left(D, sec[1])
        x = sec[2]
        # 調整 [0, 2, 5, 8, 9]、区間[1, 5]のとき、l = 1, r = 3になる。r = 2にする。
        # 調整 [0, 2, 5, 8, 9]、区間[2, 4]のとき、l = 1, r = 2になる。r = 1にする。
        r -= 1
        if r < 0:
            continue
        section_end_ix[x].append(r)
        ix = l
        while ix <= r:
            val_X = filled[ix] # 進める距離
            # 既に埋まってたら終点までスキップ
            if val_X > -1:
                _i = bisect.bisect_left(section_end_ix[val_X], ix) # section_end_ix[val_X]: 進める距離の終点のindexがのった配列
                # ix = 4、section_end_ix[val_X] = [2, 4, 7]のとき、2がかえる。

                if _i >= len(section_end_ix[val_X]):
                    # かぶってないのでよい
                    pass
                else:
                    # 終点までスキップ
                    ix = section_end_ix[val_X][_i]
            # うまってなかったら埋める
            else:
                filled[ix] = x
            ix += 1

    for x in filled:
        print(x)
main()

Submission status: Accepted

Solution code:
import heapq
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, -1, x))

event.sort()
heap = []
xs = set([])

d = [int(input()) for _ in range(q)] + [10**9 + 7]
ans = [-1] * q
index = 0
for t, query, x in event:
    while d[index] < t:
        if not xs:
            pass
        else:
            while heap:
                tmp = heapq.heappop(heap)
                if tmp in xs:
                    heapq.heappush(heap, tmp)
                    ans[index] = tmp
                    break
        index += 1

    if query == 1:
        xs.add(x)
        heapq.heappush(heap, x)
    else:
        xs.remove(x)


while index < q:
    while heap:
        tmp = heapq.heappop(heap)
        if tmp in xs:
            heapq.heappush(heap, tmp)
            ans[index] = tmp
            break
    index += 1

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q = map(int, readline().split())
    work = [0] * N
    for i in range(N):
        s, t, x = map(int, readline().split())
        work[i] = (x, s - x, t - x)
    query = list(map(int, read().split()))

    work.sort(key=itemgetter(1))
    hq = []
    ans = [0] * Q

    idx = 0
    for i, d in enumerate(query):
        while idx < N and work[idx][1] <= d:
            heappush(hq, work[idx])
            idx += 1
        while hq and hq[0][2] <= d:
            heappop(hq)
        if not hq:
            ans[i] = -1
        else:
            ans[i] = hq[0][0]

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q = map(int, readline().split())
    work = [0] * N
    for i in range(N):
        s, t, x = map(int, readline().split())
        work[i] = (x, s - x, t - x)
    query = list(map(int, read().split()))

    work.sort(key=itemgetter(1), reverse=True)
    hq = []
    ans = [0] * Q

    for i, d in enumerate(query):
        while work and work[-1][1] <= d:
            heappush(hq, work[-1])
            work.pop()
        while hq and hq[0][2] <= d:
            heappop(hq)
        if not hq:
            ans[i] = -1
        else:
            ans[i] = hq[0][0]

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append([S-X-0.5, 1, X])
    events.append([T-X-0.5, -1, X])

for i in range(Q):
    d = int(input())
    events.append([d, 0, i])

events = sorted(events)

count = defaultdict(int)
Xheap = []
heapq.heapify(Xheap)
ans = [-1 for i in range(Q)]

for e in events:
    if e[1] == 1:
        heapq.heappush(Xheap, e[2])
        count[e[2]] += 1
    elif e[1] == -1:
        count[e[2]] -= 1
    else:
        while Xheap:
            a = Xheap[0]
            if count[a] == 0:
                heapq.heappop(Xheap)
            else:
                ans[e[2]] = a
                break

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_left
n,q=map(int,input().split())
stop=[]
for i in range(n):
	s,t,x=map(int,input().split())
	stop.append((s,t,x))
stop.sort(key=lambda x:x[2])
d=[int(input())for i in range(q)]
R=[-1]*q
ans=[-1]*q
for s,t,x in stop:
	#lからrにある区間のansをxに更新したい
	l=bisect_left(d,s-x)
	r=bisect_left(d,t-x)
	while l<r:
		if R[l]==-1:#最左がまだ確定していない場合
			ans[l]=x
			R[l]=r
			l+=1
		else:
			l=R[l]#確定しているところを飛ばす
for x in ans:
	print(x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,Q = IL()
raw_data = ILL(N)
q = [-INF]+ILs(Q)+[INF]

raw_data.sort(lambda x:x[2],reverse = True)
dic = [q[i] for i in range(Q)]

class RUQ:
  def __init__(self, N, default = None):
    self.N0 = 2**(N-1).bit_length()
    self.data = [None]*(2*self.N0)
    self.INF = (-1, default)
  # 区間[l, r+1)の値をvに書き換える
  # vは(t, value)という値にする (新しい値ほどtは大きくなる)
  def update(self, l, r, v):
    L = l + self.N0; R = 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
  # a_iの現在の値を取得
  def _query(self, k):
    k += self.N0-1
    s = self.INF
    while k >= 0:
      if self.data[k]:
        s = max(s, self.data[k])
      k = (k - 1) // 2
    return s
  # これを呼び出す
  def query(self, k):
      return self._query(k)[1]

ST = RUQ(Q+2,-1)
tt = 0
for s,t,x in raw_data:
  l = bisect.bisect_left(q,s-x)
  r = bisect.bisect_left(q,t-x)
  ST.update(l,r,(tt,x))
  tt += 1
  
for i in range(Q):
  print(ST.query(i+1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,Q = IL()
raw_data = ILL(N)
q = [-INF]+ILs(Q)+[INF]

raw_data.sort(lambda x:x[2],reverse = True)
dic = [q[i] for i in range(Q)]

# N: 処理する区間の長さ

N0 = 2**((Q+2)-1).bit_length()
data = [None]*(2*N0)
INF = (-1, -1)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
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]

tt = 0
for s,t,x in raw_data:
  l = bisect.bisect_left(q,s-x)
  r = bisect.bisect_left(q,t-x)
  update(l,r,(tt,x))
  tt += 1
  
for i in range(Q):
  print(query(i+1))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_left
n,q=map(int,input().split())
stop=[]
for i in range(n):
	s,t,x=map(int,input().split())
	stop.append((s,t,x))
stop.sort(key=lambda x:x[2])
d=[int(input())for i in range(q)]
R=[-1]*q
ans=[-1]*q
for s,t,x in stop:
	#lからrにある区間のansをxに更新したい
	l=bisect_left(d,s-x)
	r=bisect_left(d,t-x)
	while l<r:
		if R[l]==-1:#最左がまだ確定していない場合
			ans[l]=x
			R[l]=r
			l+=1
		else:
			l=R[l]#確定しているところを飛ばす
for x in ans:
	print(x)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
import bisect
import sys
sys.setrecursionlimit(10**9)



# Ref: https://qiita.com/takayg1/items/b7b3f7d458915bcc7a4e
class LazySegTree:
    def __init__(self, init_val, segfunc, ide_ele = 2**31 - 1):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [None] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])



    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = v
            self.data[2 * i + 1] = v
            self.lazy[i] = None

    def update(self, l, r, x): # [l, r)
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = x
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r): # [l, r)
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res

    def gindex(self, l, r):
        l += self.num
        r += self.num
        lm = l >> (l & -l).bit_length()
        rm = r >> (r & -r).bit_length()

        while r > l:
            if l <= lm:
                yield l
            if r <= rm:
                yield r
            r >>= 1
            l >>= 1
        while l:
            yield l
            l >>= 1

def zarts(D,x): # 座標圧縮
    return bisect.bisect_left(D,x)
    

INF=10**20
def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    def segfunc(x,y):
        return min(x,y)

    v = [INF] * (Q+1)

    seg = LazySegTree(v,segfunc,ide_ele=INF)

    _X = list(enumerate(X))
    _X.sort(key=lambda x:x[1],reverse=True)
    for i,x in _X:
        l = zarts(D,S[i]-X[i])
        r = zarts(D,T[i]-X[i])
        
        if l == r: continue
        seg.update(l,r,X[i])
    

    for q in range(Q):
        d = q
        # print("d",d)
        x = seg.query(d,d+1)
        if x == INF:
            x = -1

        print(x)
    
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]"
    T = [int()] * (N)  # type: "List[int]"
    X = [int()] * (N)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, Q, S, T, X, D)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
from collections import defaultdict

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

for _ in range(Q):
    d = int(input())
    events.append((d,3,0))

events.sort()

minimumStop = [float("INF")]
stopCount = {float("INF"):1}

for sec,e,x in events:
    if e == 1:
        heappush(minimumStop,x)
        if x not in stopCount:
            stopCount[x] = 0
        stopCount[x] += 1
    if e == 3:
        while stopCount[minimumStop[0]] == 0:
            heappop(minimumStop)
        if minimumStop[0] == float("INF"):
            print(-1)
        else:
            print(minimumStop[0])
    if e == 2:
        stopCount[x] -= 1