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 random
from collections import deque
import sys
sys.stdin.readline

class TreapNode(object):
    def __init__(self, key, data):
        self.key = key
        self.ran = random.random()
        self.size = 1
        self.cnt = 1
        self.data = data
        self.left = None
        self.right = None

    def left_rotate(self):
        a = self
        b = a.right
        a.right = b.left
        b.left = a
        a = b
        b = a.left
        b.size = b.left_size() + b.right_size() + b.cnt
        a.size = a.left_size() + a.right_size() + a.cnt
        return a

    def right_rotate(self):
        a = self
        b = a.left
        a.left = b.right
        b.right = a
        a = b
        b = a.right
        b.size = b.left_size() + b.right_size() + b.cnt
        a.size = a.left_size() + a.right_size() + a.cnt
        return a

    def left_size(self):
        return 0 if self.left is None else self.left.size

    def right_size(self):
        return 0 if self.right is None else self.right.size
    
    def __repr__(self):
        return '<node key:%s ran:%f size:%d left:%s right:%s>' % (str(self.key), self.ran, self.size, str(self.left), str(self.right))


class Treap(object):
    def __init__(self):
        self.root = None

    def _insert(self, node, key, data=None):
        if node is None:
            node = TreapNode(key, data)
            return node
        node.size += 1
        if key < node.key:
            node.left = self._insert(node.left, key, data)
            if node.left.ran < node.ran:
                node = node.right_rotate()
        elif key >= node.key:
            node.right = self._insert(node.right, key, data)
            if node.right.ran < node.ran:
                node = node.left_rotate()
        #else:
        #    node.cnt += 1
        return node

    def insert(self, key, data=None):
        self.root = self._insert(self.root, key, data)
    
    def _find(self, node, key):
        if node == None:
            return None
        if node.key == key:
            return node
        if key < node.key:
            return self._find(node.left, key)
        else:
            return self._find(node.right, key)

    def find(self, key):
        return self._find(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return False
        if node.key == key:
            if node.left is None and node.right is None:
                return None
            elif node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                if node.left.ran < node.right.ran:
                    node = node.right_rotate()
                    node.right = self._delete(node.right, key)
                else:
                    node = node.left_rotate()
                    node.left = self._delete(node.left, key)
        elif key < node.key:
            node.left = self._delete(node.left, key)
        else:
            node.right = self._delete(node.right, key)
        node.size = node.left_size() + node.right_size() + node.cnt
        return node

    def delete(self, key):
        if self.find(key) is None: return False
        self.root = self._delete(self.root, key)
        return True

    def _find_kth(self, node, k):
        if node is None: return None
        if k <= node.left_size():
            return self._find_kth(node.left, k)
        if k > node.left_size() + node.cnt:
            return self._find_kth(node.right, k - node.left_size() - node.cnt)
        return node

    def find_kth(self, k):
        if k <=0 or k > self.size():
            return None
        return self._find_kth(self.root, k)

    def size(self):
        return 0 if self.root is None else self.root.size
      
      
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=Treap()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s.size():
            print(s.find_kth(1).key)
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.insert(x)
    else:
        s.delete(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.stdin.readline

def main():
  n,p=map(int,input().split())

  e=[]
  for _ in range(n):
      s,t,x = map(int,input().split())
      e.append((s-x,1,x))
      e.append((t-x,-1,x))
  e.sort()
  q = deque()
  for _ in range(p):
      q.append(int(input()))
  s=set()

  for t,f,x in e:
      while t > q[0]:
          q.popleft()
          if s:
              print(min(s))
          else:
              print(-1)
          if not q:
              sys.exit()
      if f == 1:
          s.add(x)
      else:
          s.remove(x)

  while q:
      q.pop()
      print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.stdin.readline
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e = sorted(e)
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import *
import sys

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

e=[]
heapify(e)
for _ in range(n):
    s,t,x = map(int,input().split())
    heappush(e,(s-x,1,x))
    heappush(e,(t-x,-1,x))

q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

while e:
    t,f,x = heappop(e)
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.stdin.readline
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e = sorted(e)
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
import sys
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e = sorted(e)
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
import sys
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()
#print(e)
for t,f,x in e:
    while t > q[0]:
        #print((t,f,x,q.popleft()))
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()
#print(e)
for t,f,x in e:
    while q and t > q[0]:
        #print((t,f,x,q.popleft()))
        q.popleft()
        if len(s) == 0:
            print(-1)
        else:
            print(min(s))
    if not q:
        sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
while q:
    q.pop()
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
class BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k & -k
		return ret

	def p_sum(self, i, j):
		return self.getsum(j) - self.getsum(i - 1)

	def add(self, k, x):
		while k <= self.n:
			self.bit[k] += x
			k += k & -k

	def bisect(self, x):
		i, m = 0, 1 << (self.n.bit_length() - 1)
		while m:
			t = i + m
			if t < self.n and self.bit[t] < x:
				i = t
				x -= self.bit[i]
			m //= 2
		return i + 1

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
def main():
	n, q = map(int, input().split())
	event = []
	Xs = []
	for _ in range(n):
		s, t, x = map(int, input().split())
		event.append((-2, s - x, x))
		event.append((-1, t - x, x))
		Xs.append(x)
	Xs.sort()
	for _ in range(q):
		d = int(input())
		event.append((0, d, None))
	event.sort(key=get(1))
	x_to_i = {x: i for i, x in enumerate(Xs)}
	bit = BIT(n)
	any = 0
	ans = []
	for flg, time, x in event:
		if flg == -2:
			bit.add(x_to_i[x], 1)
			any += 1
		elif flg == -1:
			bit.add(x_to_i[x], -1)
			any -= 1
		else:
			if not any:
				ans.append(-1)
			else:
				ans.append(Xs[bit.bisect(1)])
	print("\n".join(map(str, ans)))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
class BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k & -k
		return ret

	def p_sum(self, i, j):
		return self.getsum(j) - self.getsum(i - 1)

	def add(self, k, x):
		while k <= self.n:
			self.bit[k] += x
			k += k & -k

	def bisect(self, x):
		i, m = 0, 1 << (self.n.bit_length() - 1)
		while m:
			t = i + m
			if t < self.n and self.bit[t] < x:
				i = t
				x -= self.bit[i]
			m //= 2
		return i + 1

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
n,q=map(int,input().split())
event=[]
Xs=[]
for _ in range(n):
	s,t,x=map(int,input().split())
	event.append((-2,s-x,x))
	event.append((-1,t-x,x))
	Xs.append(x)
Xs.sort()
for _ in range(q):
	d=int(input())
	event.append((0,d,None))
event.sort(key=get(1))
x_to_i={x:i for i,x in enumerate(Xs)}
bit=BIT(n+1)
Xs.append(-1)
bit.add(n,1)
ans=[]
for flg,time,x in event:
	if flg==-2:
		bit.add(x_to_i[x],1)
	elif flg==-1:
		bit.add(x_to_i[x],-1)
	else:
		i=bit.bisect(1)
		ans.append(Xs[i])
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
class BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k & -k
		return ret

	def p_sum(self, i, j):
		return self.getsum(j) - self.getsum(i - 1)

	def add(self, k, x):
		while k <= self.n:
			self.bit[k] += x
			k += k & -k

	def bisect(self, x):
		i, m = 0, 1 << (self.n.bit_length() - 1)
		while m:
			t = i + m
			if t < self.n and self.bit[t] < x:
				i = t
				x -= self.bit[i]
			m //= 2
		return i + 1

import sys
input = sys.stdin.buffer.readline
from operator import itemgetter as get
n,q=map(int,input().split())
event=[]
Xs=[]
for _ in range(n):
	s,t,x=map(int,input().split())
	event.append((-2,s-x,x))
	event.append((-1,t-x,x))
	Xs.append(x)
Xs.sort()
for _ in range(q):
	d=int(input())
	event.append((0,d,None))
event.sort(key=get(1))
x_to_i={x:i for i,x in enumerate(Xs)}
bit=BIT(n+1)
Xs.append(-1)
bit.add(n,1)
ans=[]
for flg,time,x in event:
	if flg==-2:
		bit.add(x_to_i[x],1)
	elif flg==-1:
		bit.add(x_to_i[x],-1)
	else:
		i=bit.bisect(1)
		ans.append(Xs[i])
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, q = list(map(int, readline().split()))
    event = [0] * (2 * n + q)

    for i in range(n):
        s, t, x = map(int, readline().split())
        event[i * 2] = (s - x, x, 0)
        event[i * 2 + 1] = (t - x, x, 1)

    for i in range(q):
        d = int(input())
        event[2 * n + i] = (d, 0, 2)

    from operator import itemgetter
    event.sort(key=itemgetter(0))
    stop = set()
    
    for t, x, ev_type in event:
        if ev_type == 0:
            stop.add(x)
        elif ev_type == 1:
            stop.discard(x)
        else:
            if stop:
                print(min(stop))
            else:
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, q = list(map(int, readline().split()))
    event = [0] * (2 * n + q)

    for i in range(n):
        s, t, x = list(map(int, readline().split()))
        event[i * 2] = (s - x, x, 0)
        event[i * 2 + 1] = (t - x, x, 1)

    for i in range(q):
        d = int(input())
        event[2 * n + i] = (d, 0, 2)

    from operator import itemgetter
    event.sort(key=itemgetter(0))
    stop = set()

    for t, x, ev_type in event:
        if ev_type == 0:
            stop.add(x)
        elif ev_type == 1:
            stop.discard(x)
        else:
            if stop:
                print(min(stop))
            else:
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
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)]

'''
N,Q = 2*10**1,2*10**1
STX = []
order = 10**2
import random
for i in range(N):
    s = random.randint(0, order-1)
    t = random.randint(s+1,order)
    x = random.randint(1,order)
    STX.append([s,t,x])
D = sorted([random.randint(1,order) for i in range(Q)])
'''

inf = 10**12

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        self.lazy = [default] * (self.l * 2)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def update(self,k):
        if self.lazy[k] == self.default:
            return
        if k < self.l:
            self.lazy[2*k] = self.op(self.lazy[2*k], self.lazy[k])
            self.lazy[2*k+1] = self.op(self.lazy[2*k+1], self.lazy[k])
        self.data[k] = self.op(self.data[k],self.lazy[k])
        self.lazy[k] = self.default

    def set(self,i,j,val):
        def f(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return
            if i <= s and t <= j: # included
                self.lazy[k] = val
                self.update(k)
                return
            f(self,i,j,2*k,s,(s+t)//2)
            f(self,i,j,2*k+1,(s+t)//2,t)
            self.data[k] = self.op(self.data[2*k], self.data[2*k+1])
        return f(self,i,j,1,0,self.l)

    def get(self,i,j):
        def g(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return self.default # unit element
            if i <= s and t <= j: # has intersection
                return self.data[k]
            # left + right
            return self.op(g(self,i,j,2*k,s,(s+t)//2),g(self,i,j,2*k+1,(s+t)//2,t))
        return g(self,i,j,1,0,self.l)

def segsolve():
    import numpy as np
    sstx = sum([[s-x,t-x] for s,t,x in STX],[])
    sstx = sorted(set(sstx))
    comp = {s:i for i,s in enumerate(sstx)}

    d = np.searchsorted(sstx,D,side='left')

    seg = SegmentTree([inf] * len(sstx), min, inf)
    for s,t,x in STX:
        s = comp[s-x]
        t = comp[t-x]
        seg.set(s,t,x)

    for di in d:
        t = seg.get(di,di+1)
        if t == inf:
            t = -1
        print(t)

def answer():
    import bisect
    l = []
    for s,t,x in STX:
        l.append([s-x,True,x])
        l.append([t-x,False,x])
    l.sort()
    m = []

    i = 0
    for time,add,x in l:
        while i < Q and time > D[i]:
            if m:
                print(m[0])
            else:
                print(-1)
            i += 1
        if add:
            bisect.insort(m,x)
        else:
            m.remove(x)
    while i < Q:
        print(-1)
        i += 1


answer()

Submission status: Time Limit Exceeded

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

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

def main():
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが大きい順に工事区間を見て，引っかかるならば区間更新
    """

    
    N,Q=MI()
    xst2=[]#x,ごとに，Dがどの範囲なら引っかかるか(s~t)
    xi=[[0,0]for _ in range(N)]
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
        xi[i]=[x,i]
    xi.sort(reverse=True)
    
    
    
    #遅延セグ木##
    INF = 2**31-1

    LV = (Q-1).bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)

    # 伝搬対象の区間を求める
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
            lazy[i-1] = None

    # 区間[l, r)をxで更新
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = x
            if L & 1:
                lazy[L-1] = data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = min(data[2*i-1], data[2*i])

    # 区間[l, r)内の最小値を求める
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])
            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
        

    #1~10**9は大きいので，Dに与えられた値のみを見る，
    
    for i in range(N):
        ii=xi[i][1]
        x,s,t=xst2[ii][0],xst2[ii][1],xst2[ii][2]
        nums=bisect.bisect_left(D,s)
        numt=bisect.bisect_left(D,t)
        if nums!=numt:
            update(nums,numt,x)
        
    for i in range(Q):
        ans=query(i,i+1)
        if ans==INF:
            print(-1)
        else:
            print(ans)
        
    
        

main()

Submission status: Time Limit Exceeded

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

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

def main():
    mod=10**9+7
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが大きい順に工事区間を見て，引っかかるならば区間更新
    """

    
    N,Q=MI()
    xst2=[]#x,ごとに，Dがどの範囲なら引っかかるか(s~t)
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
    xst2.sort(reverse=True)
    
    
    #遅延セグ木##
    INF = 2**31-1

    LV = (Q-1).bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)

    # 伝搬対象の区間を求める
    def gindex(l, r):
        L = (l + N0) >> 1; R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1

    # 遅延伝搬処理
    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
            lazy[i-1] = None

    # 区間[l, r)をxで更新
    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = x
            if L & 1:
                lazy[L-1] = data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = min(data[2*i-1], data[2*i])

    # 区間[l, r)内の最小値を求める
    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])
            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
        

    #1~10**9は大きいので，Dに与えられた値のみを見る，
    
    for i in range(N):
        x,s,t=xst2[i][0],xst2[i][1],xst2[i][2]
        nums=bisect.bisect_left(D,s)
        numt=bisect.bisect_left(D,t)
        update(nums,numt,x)
        
    for i in range(Q):
        ans=query(i,i+1)
        if ans==INF:
            print(-1)
        else:
            print(ans)
        
    
        

main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
N,Q,*L = map(int, open(0).read().split())
D = L[3*N:]
ls = [0]*N
for i in range(N):
  s,t,x = L[3*i],L[3*i+1],L[3*i+2]
  ls[i] = (x,s,t)
ls.sort()
line = [0]*(2*N)
for i in range(N):
  x,s,t = ls[i]
  line[2*i] = (s-x,0,i)
  line[2*i+1] = (t-x,1,i)
line.sort()
road = [c[0] for c in line]
inf = [0]*(2*N)
m = 0
for i in range(2*N):
  d,p,j = line[i]
  if p:
    m -= 1<<j
  else:
    m += 1<<j
  inf[i] = m
for d in D:
  i = bisect_right(road,d)
  if i==2*N or i==0:
    print(-1)
    continue
  m = inf[i-1]
  s = m&-m
  if s==0:
    print(-1)
  else:
    ind = len(bin(s)[2:])-1
    print(ls[ind][0])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
N,Q,*L = map(int, open(0).read().split())
D = L[3*N:]
ls = [0]*N
for i in range(N):
  s,t,x = L[3*i],L[3*i+1],L[3*i+2]
  ls[i] = (x,s,t)
ls.sort()
line = [0]*(2*N)
road = [0]*(2*N)
for i in range(N):
  x,s,t = ls[i]
  line[2*i] = (s-x,0,i)
  line[2*i+1] = (t-x,1,i)
  road[2*i] = s-x
  road[2*i+1] = t-x
line.sort()
road.sort()
inf = [0]*(2*N)
m = 0
for i in range(2*N):
  d,p,j = line[i]
  if p:
    m -= 1<<j
  else:
    m += 1<<j
  inf[i] = m
for d in D:
  i = bisect_right(road,d)
  if i==2*N or i==0:
    print(-1)
    continue
  m = inf[i-1]
  s = m&-m
  if s==0:
    print(-1)
  else:
    ind = len(bin(s)[2:])-1
    print(ls[ind][0])

Submission status: Time Limit Exceeded

Solution code:

# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)

Submission status: Time Limit Exceeded

Solution code:

# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
events = sorted(events, key=itemgetter(0,1), reverse=True)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)

Submission status: Time Limit Exceeded

Solution code:

# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
events = sorted(events, key=itemgetter(0,1), reverse=True)
ans = [-1] * q
events.sort()
works = set()
for t, e, x in events:
    if e == 1:
        works.add(x)
    elif e == 0:
        works.remove(x)
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            ans[x] = min(works)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:

# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  0 eve削除
工事 start   1 eve追加
di start     2
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
X = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    events.append((s-x,1,x))
    events.append((t-x,-1,x))
    
for i in range(q):
    d = int(input())
    events.append((d,2,i))

ans = [-1] * q
events.sort()
works = set()
for t, e, x in events:
    if e == 1:
        works.add(x)
    elif e == -1:
        works.remove(x)
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            ans[x] = min(works)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q  = map(int, input().split())
events = []
for i in range(n):
    s,t,x = map(int, input().split())
    events.append((s-x,1,x))
    events.append((t-x,-1,x))
    
for i in range(q):
    d = int(input())
    events.append((d,2,i))
ans = [-1] * q
events.sort()
works = set()
for t, e, x in events:
    if e == 1:
        works.add(x)
    elif e == -1:
        works.remove(x)
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            ans[x] = min(works)
print(*ans)