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.readline
inf = float('inf')
mod = 10**9+7


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

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

    event.sort(key=lambda x: x[0])
    occur = set()
    occur_priority = []
    for e in event:
        if e[1] == 1:
            occur.add(e[2])
            heapq.heappush(occur_priority, e[2])
        elif e[1] == -1:
            if e[2] in occur:
                occur.remove(e[2])
        # クエリ
        elif e[1] == 0:
            if occur:
                while 1:
                    if occur_priority[0] in occur:
                        min_occur = occur_priority[0]
                        break
                    else:
                        heapq.heappop(occur_priority)
                print(min_occur)
            else:
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))
    
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop
        
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
from operator import itemgetter
from bisect import bisect_left


def main():
    n, q = list(map(int, input().split()))
    stops = []
    for _ in range(n):
        s, t, x = list(map(int, input().split()))
        stops.append((s, t, x))
    delay = []
    for i in range(q):
        delay.append(int(input()))

    stops = sorted(stops, key=itemgetter(2))
    delay = sorted(delay)

    result = [-1] * q
    skips = [-1] * q

    for s, t, x in stops:
        sx = bisect_left(delay, s - x)
        tx = bisect_left(delay, t - x)
        while sx < tx:
            if skips[sx] == -1:
                result[sx] = x
                skips[sx] = tx
                sx += 1
            else:
                sx = skips[sx]

    for r in result:
        print(r)


main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input())
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

n, q = map(int, input().split())
events = []
for _ in range(n):
    s, t, x = map(int, input().split())
    events.append((s-x-0.5, 1, x)) # start construction
    events.append((t-x-0.5, -1, x)) # end construction

for i in range(q):
    d = int(input())
    events.append((d, 0, i)) # query
    
events = sorted(events)
is_stop = False
stops = set()
min_stop = float('inf')
ans = [-1]*q
for t, e, x in events: # time, event, distance/index
    if e > 0:
        stops.add(x)
        if x < min_stop:
            min_stop = x
            is_stop = True
    elif e < 0:
        stops.remove(x)
        if min_stop == x:
            is_stop = False
    elif len(stops) > 0:
        if not is_stop:
             min_stop = min(stops)
             is_stop = True
        ans[x] = min_stop
         
print('\n'.join(map(str, ans)))

Submission status: Accepted

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

n, q = map(int, input().split())
events = []
for _ in range(n):
    s, t, x = map(int, input().split())
    events.append((s-x-0.5, 's', x)) # start construction
    events.append((t-x-0.5, 'e', x)) # end construction

for i in range(q):
    d = int(input())
    events.append((d, 'q', i)) # query
    
events = sorted(events)
is_stop = False
stops = set()
min_stop = float('inf')
ans = [-1]*q
for t, e, x in events: # time, event, distance/index
    if e == 's':
        stops.add(x)
        if x < min_stop:
            min_stop = x
            is_stop = True
    elif e == 'e':
        stops.remove(x)
        if min_stop == x:
            is_stop = False
    elif len(stops) > 0:
        if not is_stop:
             min_stop = min(stops)
             is_stop = True
        ans[x] = min_stop
         
print('\n'.join(map(str,ans)))

Submission status: Accepted

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

n, q = map(int, input().split())
events = []
for _ in range(n):
    s, t, x = map(int, input().split())
    events.append((s-x-0.5, 's', x)) # start construction
    events.append((t-x-0.5, 'e', x)) # end construction

for i in range(q):
    d = int(input())
    events.append((d, 'q', i)) # query
    
events = sorted(events)
is_stop = False
stops = set()
min_stop = float('inf')
ans = [-1]*q
for t, e, x in events: # time, event, distance/index
    if e == 's':
        stops.add(x)
        if x < min_stop:
            min_stop = x
            is_stop = True
    elif e == 'e':
        stops.remove(x)
        if min_stop == x:
            is_stop = False
    elif len(stops) > 0:
        if not is_stop:
             min_stop = min(stops)
             is_stop = True
        ans[x] = min_stop
         
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

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

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

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

Submission status: Accepted

Solution code:
import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

ans = [-1 for _ in range(Q)]
nexts = [-1 for _ in range(Q)]

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

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

Submission status: Accepted

Solution code:
import bisect
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]

ans = [-1 for _ in range(Q)]
nexts = [-1 for _ in range(Q)]

for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = max(0, bisect.bisect_left(D, s - x))
    hi = min(len(D), bisect.bisect_left(D, t - x))

    p = lo
    while p < hi:
        if nexts[p] == -1:
            ans[p] = x
            nexts[p] = hi
            p += 1
        else:
            prev = p
            p = nexts[p]
            nexts[prev] = hi

for a in ans:
    print(int(a))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left



N,Q = map(int, input().split())
STX = [None] * N
for i in range(N):
  s,t,x = map(int, input().split())
  STX[i] = [x,s,t]
STX.sort()
Dn = [None] * (Q+1)
for i in range(Q):
  Dn[i] = int(input())
Dn[Q] = 10**10

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in STX:
  ss = bisect_left(Dn, s - x)
  tt = bisect_left(Dn, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

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

Submission status: Accepted

Solution code:
import sys

n, q = map(int, input().split())
lines = sys.stdin.readlines()
coordinates = set()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    sx = s - x
    tx = t - x
    kkk.append((x, sx, tx))
    coordinates.add(sx)
    coordinates.add(tx)
kkk.sort()
ddd = list(map(int, lines[n:]))
coordinates.update(ddd)
coordinates = {d: i for i, d in enumerate(sorted(coordinates))}
coord_len = len(coordinates)

ans = [-1] * coord_len
skip = [-1] * coord_len
for x, sx, tx in kkk:
    ss = coordinates[sx]
    tt = coordinates[tx]
    while ss < tt:
        sk = skip[ss]
        if sk == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = sk
print('\n'.join(map(str, map(ans.__getitem__, map(coordinates.get, ddd)))))

Submission status: Accepted

Solution code:
def e_roadwork(N, Q, Construction, D):
    from bisect import bisect_left
    from operator import itemgetter
    ans = [-1] * Q
    skip = [-1] * Q

    Construction.sort(key=itemgetter(2))

    for s, t, x in Construction:
        l = bisect_left(D, s - x)
        r = bisect_left(D, t - x)
        t = l
        while t < r:
            if skip[t] == -1:
                ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
                skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
                t += 1
            else:
                t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
    return ' '.join(map(str, ans))
    # 参考: https://atcoder.jp/contests/abc128/submissions/5654623

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

Submission status: Accepted

Solution code:
import sys, collections, heapq
def single_input(F): return F.readline().strip("\n")
def line_input(F): return F.readline().strip("\n").split()

def solve():
    F = sys.stdin
    N, Q = map(int, line_input(F))
    event = []
    for i in range(N):
        s, t, x = map(int, line_input(F))
        event.append((s-x, 1, x))
        event.append((t-x,-1, x))
    for i in range(Q):
        d = int(single_input(F))
        event.append((d, 2, d))
    event.sort()
    candidate = []
    heapq.heapify(candidate)
    stop = collections.defaultdict(int)
    ans = ""
    for time, parameter, co in event:
        if parameter == 1:
            heapq.heappush(candidate, co)
            stop[co] += 1
        elif parameter == -1:
            stop[co] -= 1
        else:
            while candidate:
                x = heapq.heappop(candidate)
                if stop[x] > 0:
                    heapq.heappush(candidate, x)
                    ans += str(x) + "\n"
                    break
            else: ans += "-1\n"
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys, collections, heapq
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((s-x, 1, x))
        event.append((t-x,-1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, d))
    event.sort()
    candidate = []
    heapq.heapify(candidate)
    stop = collections.defaultdict(int)
    ans = ""
    for time, parameter, co in event:
        if parameter == 1:
            heapq.heappush(candidate, co)
            stop[co] += 1
        elif parameter == -1:
            stop[co] -= 1
        else:
            while candidate:
                x = heapq.heappop(candidate)
                if stop[x] > 0:
                    heapq.heappush(candidate, x)
                    ans += str(x) + "\n"
                    break
            else: ans += "-1\n"
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(q, t)
        t = []
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from operator import itemgetter

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

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

stx.sort(key=itemgetter(2))

for s, t, x in stx:
    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]

for x in ans:
    print(x)

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.N = N
        self.tree = [0]*(self.N + 1)
        self.n = 1
        while self.n <= N:
            self.n *= 2
        self.n //= 2

    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.N:
            self.tree[i] += x
            i += (i & -(i))

    def lower_bound(self, val):
        if val <= 0:
            return 0
        res = 0
        k = self.n
        while k:
            if res + k <= self.N and self.tree[res + k] < val:
                val -= self.tree[res + k]
                res += k
            k //= 2
        return res + 1

class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.lower_bound(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_left
n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for _ in range(n)]
STX.sort(key=lambda x: x[2])
D=[int(input()) for _ in range(q)]
Ans=[-1]*q; Jump=[-1]*q
for s,t,x in STX:
    l=bisect_left(D,s-x)
    r=bisect_left(D,t-x)
    while l<r:
        s=Jump[l]
        if s==-1:
            Ans[l]=x
            Jump[l]=r
            l+=1
        else:
            l=s
print(*Ans,sep='\n')

Submission status: Accepted

Solution code:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)

    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


class DammyMap:

    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))

        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]


    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)
 
dmap = DammyMap(D)
 
for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
 
print(*ans, sep="\n")

Submission status: Accepted

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

N, Q = map(int, input().split())
events = []
for iR in range(N):
    S, T, X = map(int, input().split())
    events.append((S-X, T-X, X))
events.sort()

iE = 0
anss = []
PQ = []
for _ in range(Q):
    D = int(input())
    while iE < N and events[iE][0] <= D:
        tmSt, tmEn, x = events[iE]
        heappush(PQ, (x, tmEn))
        iE += 1

    xMin = -1
    while PQ:
        x, tmEn = heappop(PQ)
        if tmEn > D:
            xMin = x
            heappush(PQ, (x, tmEn))
            break
    anss.append(xMin)

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

Submission status: Accepted

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


n,q = list(map(int,input().split()))
lines = sys.stdin.readlines()
stx = []
for line in lines[:n]:
    s,t,x = map(int,line.split())
    stx.append((x,s,t))
stx.sort()
D = list(map(int,lines[n:]))
ans = [-1]*q
skip = [-1]*q
for x,s,t in stx:
    ss = bisect_left(D,s-x)
    tt = bisect_left(D,t-x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss]=x
            skip[ss]=tt
            ss += 1
        else:
            ss = skip[ss]
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_left
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

n,q=map(int,input().split())
seg=SegmentTree(q,min,float('inf'))
STX=[list(map(int,input().split())) for _ in range(n)]
D=[int(input()) for _ in range(q)]
for s,t,x in STX:
    seg.rangeupdate(bisect_left(D,s-x),bisect_left(D,t-x),x)
for i in range(q):
    print(-1 if seg.getvalue(i)==float('inf') else seg.getvalue(i))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        sk = skip[ss]
        if sk == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = sk
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        sk = skip[ss]
        if sk == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            skip[ss] = max(sk, tt)
            ss = sk
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush

n, q = map(int, input().split())
lines = sys.stdin.readlines()
events = []
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    events.append((s - x, 2, x))
    events.append((t - x, 1, x))
for line in lines[n:]:
    events.append((int(line), 3))
events.sort()

constructing = []
available = set()
buf = []
for ev in events:
    if ev[1] == 2:
        heappush(constructing, ev[2])
        available.add(ev[2])
    elif ev[1] == 1:
        available.remove(ev[2])
    else:
        if not available:
            buf.append(-1)
        else:
            while constructing[0] not in available:
                heappop(constructing)
            buf.append(constructing[0])
print('\n'.join(map(str, buf)))

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
# The person start in this location will be stopped.
work = []
for i in range(N):
    start, end, pos = map(int, input().split())
    work.append((start - pos - 0.5, end - pos - 0.5, pos))
work.sort(key=lambda x: x[0])
depart_time = [int(input()) for _ in range(Q)]
heap = []
end_time = {}
import heapq
i = 0
for depart in depart_time:
    while i < len(work) and work[i][0] < depart:
        start, end, pos = work[i]
        heapq.heappush(heap, pos)
        end_time[pos] = end
        i += 1
    while heap and end_time[heap[0]] < depart:
        heapq.heappop(heap)
    if heap: print(heap[0])
    else: print(-1)

Submission status: Accepted

Solution code:
import bisect

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

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

ans = [-1 for _ in range(q)]
nxt = [-1 for _ in range(q)]
for rw in rws:
	st = bisect.bisect_left(ds, rw[0] - rw[2])
	en = bisect.bisect_left(ds, rw[1] - rw[2])
	while st < en:
		if nxt[st] == -1:
			ans[st] = rw[2]
			nxt[st] = en
			st += 1
		else:
			st = nxt[st]

for a in ans:
	print(a)

Submission status: Accepted

Solution code:
#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

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)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = [] # heapでソートを保つ
added = defaultdict(int) # 入ってる個数

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    added[c] -= 1
  elif b&1: # b == 1
    heappush(se,c)
    added[c] += 1
  else: # b == 2
    while se and added[se[0]] == 0:
      heappop(se)
    answer[c] = se[0] if se else -1

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