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: Time Limit Exceeded

Solution code:
import heapq as hq
def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [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 = []
  push = hq.heappush
  pop = hq.heappop
  cnt = 0
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      push(q, L[cnt])
      cnt += 1
    t = pop(q)
    while t[2] <= D[i]:
      if q == []:
        print(-1)
        break
      t = pop(q)
    else:
      print(t[0])
    push(q, t)

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq
def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [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 = []
  push = hq.heappush
  pop = hq.heappop
  push(q, [10**10, -1, 10**10])
  cnt = 0
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      push(q, L[cnt])
      cnt += 1
    t = pop(q)
    while t[2] <= D[i]:
      t = pop(q)
    if t[0] != 10**10:
      print(t[0])
    else:
      print(-1)
    push(q, t)

main()

Submission status: Time Limit Exceeded

Solution code:
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)]

e = []

for s, t, x in stx:
    e.append([s-x, 1, x])
    e.append([t-x, -1, x])

e.sort()
e.append([10 ** 9, 1, 10 ** 9])

h = set()
h.add(10 ** 9)
i = 0

for p in d:
    while e[i][0] <= p:
        if e[i][1] == 1:
            h.add(e[i][2])
        else:
            h.remove(e[i][2])
        i += 1
    ans = min(h)
    if ans == 10 ** 9:
        print(-1)
    else:
        print(min(h))

Submission status: Time Limit Exceeded

Solution code:
import heapq
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)]

# (d, x, 0 or 1) のリスト
events = []

for xi, [s, t, x] in enumerate(STX):
    # [lo, hi) に出発した人は x で止まる
    lo = s - x
    hi = t - x
    events.append((lo, x, 1))  # 追加
    events.append((hi, x, 0))  # 削除

events.sort()
ev = 0
closes = set()
heap = []
for d in D:
    while ev < len(events) and events[ev][0] <= d:
        t, x, op = events[ev]
        if op == 1:
            closes.add(x)
            heapq.heappush(heap, x)
        else:
            closes.remove(x)
        ev += 1
    while heap and heap[0] not in closes:
        heapq.heappop(heap)
    if heap:
        print(heap[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

#stx.sort(reverse=True, key=itemgetter(2))

e = []

for s, t, x in stx:
    e.append([s-x, 1, x])
    e.append([t-x, -1, x])

e.sort()
e.append([10 ** 9, 1, 10 ** 9])

h = set()
h.add(10 ** 9)
i = 0

for p in d:
    while e[i][0] <= p:
        if e[i][1] == 1:
            h.add(e[i][2])
        else:
            h.remove(e[i][2])
        i += 1
    ans = min(h)
    if ans == 10 ** 9:
        print(-1)
    else:
        print(min(h))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

# (d, x, 0 or 1) のリスト
events = []

for xi, [s, t, x] in enumerate(STX):
    # [lo, hi) に出発した人は x で止まる
    lo = s - x
    hi = t - x
    events.append((lo, x, 1))  # 追加
    events.append((hi, x, 0))  # 削除

events.sort()
ev = 0
closes = set()
for d in D:
    while ev < len(events) and events[ev][0] <= d:
        t, x, op = events[ev]
        if op == 1:
            closes.add(x)
        else:
            closes.remove(x)
        ev += 1
    if closes:
        print(min(closes))
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

stx.sort(reverse=True, key=itemgetter(2))

for s, t, x in stx:
    L = bisect_left(d, s-x)
    R = bisect_left(d, t-x)
    for i in range(L, R):
        ans[i] = x

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline

## input
N,Q = map(int, readl().rstrip().split())
STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
Dn = [None for _ in range(Q+1)]
for i in range(Q):
  Dn[i] = int(readl().rstrip())
Dn[Q] = 10**10
ans = []

for s,t,x in sorted(STX,key=lambda x:x[2]):
  l = r = bisect_left(Dn,s-x)
  t -= x
  while Dn[r] < t:
    heappush(ans, (Dn[r],x))
    r += 1
  del Dn[l:r]

for d in Dn[:-1]:
  heappush(ans, (d,-1))

[print(heappop(ans)[1]) for _ in range(Q)]

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = sorted([list(map(int, readl().rstrip().split())) for _ in range(N)],key=lambda x:x[2])
  Dn = [None for _ in range(Q+1)]
  for i in range(Q):
    Dn[i] = int(readl().rstrip())
  Dn[Q] = 10**10
  ans = []

  for s,t,x in STX:
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
from bisect import*
from heapq import*

n,q=map(int,input().split())
event=[]
stopped=set([-1])

def doevent(l):
    global stopped
    if l[1]==1:
        if stopped=={-1}:
            stopped=set()
        stopped.add(l[2])
    elif l[1]==-1:
        if l[2] in stopped:
            stopped.remove(l[2])
        if len(stopped)==0:
            stopped={-1}
            
for i in range(n):
    s,t,x=map(int,input().split())
    heappush(event,(s-x,1,x))
    heappush(event,(t-x,-1,x))
heappush(event,(-float("inf"),"x","x"))
heappush(event,(float("inf"),"x","x"))
event.sort(key=lambda x:x[0])
query=[bisect_right([i[0]for i in event],int(input()))-1 for i in range(q)]+[float("inf")]
#print(query)
c=0
#print(event)
for i in range(2*n+1):
    doevent(event[i])
#    print(stopped)
    while i==query[c]:
        print(min(stopped))
        c+=1

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [[None,None,None] for _ in range(N)]
  for i in range(N):
    STX[i] = list(map(int, readl().rstrip().split()))
  Dn = [None for _ in range(Q+1)]
  for i in range(Q):
    Dn[i] = int(readl().rstrip())
  Dn[Q] = 10**10
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

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 OfflineSortedSet:
	
    def __init__(self, all_vals):
        self.keys = sorted(set(all_vals))
        self.max_key = max(self.keys)
        self.key_to_index = {k:i for i, k in enumerate(self.keys, start=1)}
        self.keys_num = len(self.keys)

        self.bit = BIT(self.keys_num)
        self.hash_set = set()

        self.add_bit = self.bit.add
        self.sum_bit = self.bit.sum
        self.lower_bound_bit = self.bit.lower_bound
        self.add_hash_set = self.hash_set.add
        self.remove_hash_set = self.hash_set.remove

    def exists(self, val):
        return val in self.hash_set

    def add(self, val):
        if val in self.hash_set:
            return
        
        self.add_hash_set(val)
        self.add_bit(self.key_to_index[val], 1)

    def remove(self, val):
        if val not in self.hash_set:
            return

        self.remove_hash_set(val)
        self.add_bit(self.key_to_index[val], -1)

    def lower_bound(self, val):
        idx = bisect_left(self.keys, val)
        tar = self.sum_bit(idx)
        res = self.lower_bound_bit(tar + 1) - 1
        if res < 0 or res >= self.keys_num:
            res = self.keys_num
        return res

def main():
    N, Q = inpl()
    hoge = [inpl() for _ in range(N)]
    X = [0]*N

    v = [0]*(2*N)
    for i in range(N):
        s, t, X[i] = hoge[i]
        v[2*i] = (s - X[i], 1, X[i])
        v[2*i+1] = (t - X[i], -1, X[i])
    v = sorted(v)

    se = OfflineSortedSet(X)
    del X

    idx = 0
    D = [int(input()) for _ in range(Q)]
    ans = [0]*Q
    for i, d in enumerate(D):
        while idx < len(v):
            t, com, x = v[idx]
            if t > d:
                break
            if com == 1:
                se.add(x)
            else:
                se.remove(x)
            idx += 1
        ans[i] = -1 if len(se.hash_set) == 0 else se.keys[se.lower_bound(-10000000000)]
    print(*ans, sep="\n")
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [None for _ in range(Q+1)]
  for i in range(Q):
    Dn[i] = int(readl().rstrip())
  Dn[Q] = 10**10
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

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 OfflineSortedSet:
	
    def __init__(self, all_vals):
        self.keys = sorted(set(all_vals))
        self.max_key = max(self.keys)
        self.key_to_index = {k:i for i, k in enumerate(self.keys, start=1)}
        self.keys_num = len(self.keys)

        self.bit = BIT(self.keys_num)
        self.hash_set = set()

        self.add_bit = self.bit.add
        self.sum_bit = self.bit.sum
        self.lower_bound_bit = self.bit.lower_bound
        self.add_hash_set = self.hash_set.add
        self.remove_hash_set = self.hash_set.remove

    def exists(self, val):
        return val in self.hash_set

    def add(self, val):
        if val in self.hash_set:
            return
        
        self.add_hash_set(val)
        self.add_bit(self.key_to_index[val], 1)

    def remove(self, val):
        if val not in self.hash_set:
            return

        self.remove_hash_set(val)
        self.add_bit(self.key_to_index[val], -1)

    def lower_bound(self, val):
        idx = bisect_left(self.keys, val)
        tar = self.sum_bit(idx)
        res = self.lower_bound_bit(tar + 1) - 1
        if res < 0 or res >= self.keys_num:
            res = self.keys_num
        return res

def main():
    N, Q = inpl()
    X = [0]*N

    v = [0]*(2*N)
    for i in range(N):
        s, t, X[i] = inpl()
        v[2*i] = (s - X[i], 1, X[i])
        v[2*i+1] = (t - X[i], -1, X[i])
    v = sorted(v)

    se = OfflineSortedSet(X)
    del X

    idx = 0
    for i in range(Q):
        d = int(input())
        while idx < len(v):
            t, com, x = v[idx]
            if t > d:
                break
            if com == 1:
                se.add(x)
            else:
                se.remove(x)
            idx += 1
        print(-1 if len(se.hash_set) == 0 else se.keys[se.lower_bound(-10000000000)])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  STX = sorted(STX,key=lambda x:x[2])
  for s,t,x in STX:
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
from bisect import*
from collections import deque

n,q=map(int,input().split())
event=deque([])
stopped=set([-1])

def doevent(l):
    global stopped
    if l[1]==1:
        if stopped=={-1}:
            stopped=set()
        stopped.add(l[2])
    elif l[1]==-1:
        if l[2] in stopped:
            stopped.remove(l[2])
        if len(stopped)==0:
            stopped={-1}
            
for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))
event.append((-float("inf"),"x","x"))
event.append((float("inf"),"x","x"))
event=list(event)
event.sort(key=lambda x:x[0])
eventtime=[i[0]for i in event]
#print(eventtime)
query=[bisect_right(eventtime,int(input()))-1 for i in range(q)]+[float("inf")]
#print(query)
c=0
#print(event)
for i in range(2*n+1):
    doevent(event[i])
    while i==query[c]:
        print(min(stopped))
        c+=1

Submission status: Time Limit Exceeded

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

n,q=map(int,input().split())
event=[]
stopped=set([-1])

def doevent(l):
    global stopped
    if l[1]==1:
        if stopped=={-1}:
            stopped=set()
        stopped.add(l[2])
    elif l[1]==-1:
        if l[2] in stopped:
            stopped.remove(l[2])
        if len(stopped)==0:
            stopped={-1}
            
for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))
event.append((-float("inf"),"x","x"))
event.append((float("inf"),"x","x"))
event.sort(key=lambda x:x[0])
eventtime=[i[0]for i in event]
#print(eventtime)
query=[bisect_right(eventtime,int(input()))-1 for i in range(q)]+[float("inf")]
#print(query)
c=0
#print(event)
for i in range(2*n+1):
    doevent(event[i])
    while i==query[c]:
        print(min(stopped))
        c+=1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = bisect_left(Dn,s-x)
    t -= x
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, readl().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while(len(ans)>0):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, readl().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  n=len(ans)
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []
  STX=sorted(STX)
  
  for x,s,t in STX:
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans) > 0:
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans) > 0:
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    Dn = Dn[:l]+Dn[r:]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans) > 0:
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      heappush(ans, (Dn[l],x))
      del Dn[l]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans) > 0:
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin



def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = {}

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      del Dn[l]

  for d in Dn[:-1]:
    ans[d] = -1

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
kouji.sort(key=lambda x:x[2])
D=[int(input()) for i in range(Q)]
MAXIDX=D[-1]
L=1
while L<Q:
    L*=2
inf=float('inf')
D+=[inf]*(L-Q)
K=2*L-1

idx=[0]*K
Range=[(inf,inf)]*K
Min=[inf]*K

idx[0]=(0,L-1)
Range[0]=(D[idx[0][0]],D[idx[0][1]])
for k in range(L-1):
    l,r=idx[k]
    idx[2*k+1]=(l,(l+r)//2)
    idx[2*k+2]=((l+r)//2+1,r)
    Range[2*k+1]=(D[idx[2*k+1][0]],D[idx[2*k+1][1]])
    Range[2*k+2]=(D[idx[2*k+2][0]],D[idx[2*k+2][1]])
def renew(b,e,x,k):
    if b>MAXIDX:
        return
    global Min
    if e<Range[k][0] or b>Range[k][1]:
        return
    b=max(Range[k][0],b)
    e=min(Range[k][1],e)
    if b==Range[k][0] and e==Range[k][1]:
        Min[k]=min(Min[k],x)
        return
    if Range[2*k+2][0]>e:
        if Min[2*k+1]<=x:
            return
        renew(max(b,Range[2*k+1][0]),min(e,Range[2*k+1][1]),x,2*k+1)
    elif Range[2*k+1][1]<b:
        if Min[2*k+2]<=x:
            return
        renew(max(b,Range[2*k+2][0]),min(e,Range[2*k+2][1]),x,2*k+2)
    else:
        renew(max(b,Range[2*k+1][0]),Range[2*k+1][1],x,2*k+1)
        renew(Range[2*k+2][0],min(e,Range[2*k+2][1]),x,2*k+2)
    return
for b,e,x in kouji:
    renew(b,e,x,0)
def get(q):
    global Min
    ans=10**10
    now=q
    while True:
        if now==0:
            break
        ans=min(ans,Min[now])
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
kouji.sort(key=lambda x:x[2])
D=[int(input()) for i in range(Q)]
L=1
while L<Q:
    L*=2
inf=float('inf')
D+=[inf]*(L-Q)
K=2*L-1

idx=[0]*K
Range=[(inf,inf)]*K
Min=[inf]*K

idx[0]=(0,L-1)
Range[0]=(D[idx[0][0]],D[idx[0][1]])
MAXIDX=D[-1]
for k in range(L-1):
    l,r=idx[k]
    idx[2*k+1]=(l,(l+r)//2)
    idx[2*k+2]=((l+r)//2+1,r)
    Range[2*k+1]=(D[idx[2*k+1][0]],D[idx[2*k+1][1]])
    Range[2*k+2]=(D[idx[2*k+2][0]],D[idx[2*k+2][1]])
def renew(b,e,x,k):
    if b>MAXIDX:
        return
    global Min
    if e<Range[k][0] or b>Range[k][1]:
        return
    b=max(Range[k][0],b)
    e=min(Range[k][1],e)
    if b==Range[k][0] and e==Range[k][1]:
        Min[k]=min(Min[k],x)
        return
    if Range[2*k+2][0]>e:
        if Min[2*k+1]<=x:
            return
        renew(max(b,Range[2*k+1][0]),min(e,Range[2*k+1][1]),x,2*k+1)
    elif Range[2*k+1][1]<b:
        if Min[2*k+2]<=x:
            return
        renew(max(b,Range[2*k+2][0]),min(e,Range[2*k+2][1]),x,2*k+2)
    else:
        renew(max(b,Range[2*k+1][0]),Range[2*k+1][1],x,2*k+1)
        renew(Range[2*k+2][0],min(e,Range[2*k+2][1]),x,2*k+2)
    return
for b,e,x in kouji:
    renew(b,e,x,0)
def get(q):
    global Min
    ans=10**10
    now=q
    while True:
        if now==0:
            break
        ans=min(ans,Min[now])
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))