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:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop

N,Q=map(int, sys.stdin.readline().split())

RW=[]	#  Roadwork: 道路工事を行っている場所　(開始時間、終了時間、x座標)
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	RW.append( (max(0,s-x) , max(0,t-1-x),x) )
RW.sort()

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]	# Q人の歩き出す時刻
D.sort()


d=0
for d in D:
	hq=[]
	for s,t,x in RW:
		if s<=d<=t:
			heappush(hq, x)

	try:
		print hq[0]
	except:
		print -1

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline
INF = float("inf")


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [int(input()) for _ in range(Q)]
    ans = [INF] * Q
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        for idx in range(l, r):
            ans[idx] = min(X, ans[idx])
    for a in ans:
        if a == INF:
            print(-1)
        else:
            print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        for idx in range(l, r):
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    DI = [(int(input()), i) for i in range(Q)]
    DI.sort(key=itemgetter(0))
    D = [0] * Q
    revD = [0] * Q
    for i in range(Q):
        D[i], revD[i] = DI[i]
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        for i in range(l, r):
            idx = revD[i]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from operator import itemgetter


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [(int(input()), i) for i in range(Q)]
    D.sort(key=itemgetter(0))
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, (S-X, -1))
        r = bisect_right(D, (T-X, -1))
        for i in range(l, r):
            idx = D[i][1]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [(int(input()), i) for i in range(Q)]
    D.sort(key=itemgetter(0))
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, (S-X, -1))
        r = bisect_right(D, (T-X, -1))
        for i in range(l, r):
            idx = D[i][1]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


class BinTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root:
            self.root.insert(value)
        else:
            self.root = BinTreeNode(value)

    def exists(self, value):
        if self.root:
            return self.root.exists(value)
        else:
            return False

    def min(self):
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

    def remove(self, value):
        if self.root:
            self.root = self.root.remove(value)

    def sort(self):
        if self.root:
            return self.__walk(self.root)
        else:
            return []

    def __walk(self, target):
        ret = []
        if target.left:
            ret += self.__walk(target.left)
        ret += [target.value]
        if target.right:
            ret += self.__walk(target.right)
        return ret


class BinTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

    def insert(self, value):
        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = BinTreeNode(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = BinTreeNode(value)
        self.rebuild()

    def rebuild(self):
        lheight = BinTreeNode.height(self.left)
        rheight = BinTreeNode.height(self.right)
        if lheight - rheight >= 2:
            if BinTreeNode.height(self.left.left) < BinTreeNode.height(self.left.right):
                BinTreeNode.turn_left(self.left)
            BinTreeNode.turn_right(self)
        elif rheight - lheight >= 2:
            if BinTreeNode.height(self.right.left) > BinTreeNode.height(self.right.right):
                BinTreeNode.turn_right(self.right)
            BinTreeNode.turn_left(self)
        else:
            BinTreeNode.update_height(self)

    @classmethod
    def turn_left(cls, root):
        gl = root.right.left
        gr = root.right.right
        v = root.value
        r = root.right
        rv = r.value
        r.left = root.left
        r.right = gl
        r.value = v
        root.left = root.right
        root.value = rv
        root.right = gr
        BinTreeNode.update_height(root.right)
        BinTreeNode.update_height(root)

    @classmethod
    def turn_right(cls, root):
        gl = root.left.left
        gr = root.left.right
        v = root.value
        l = root.left
        lv = l.value
        l.right = root.right
        l.left = gr
        l.value = v
        root.right = root.left
        root.value = lv
        root.left = gl
        BinTreeNode.update_height(root.left)
        BinTreeNode.update_height(root)

    @classmethod
    def height(cls, root):
        return root.height if root is not None else 0

    @classmethod
    def update_height(cls, root):
        if root is None:
            return
        root.height = max(BinTreeNode.height(root.left),
                          BinTreeNode.height(root.right)) + 1

    def exists(self, value):
        if value == self.value:
            return True
        elif value < self.value:
            if self.left:
                return self.left.exists(value)
            else:
                return False
        elif value > self.value:
            if self.right:
                return self.right.exists(value)
            else:
                return False

    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self.value

    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self.value

    def __removenode(self):
        if self.left and self.right:
            value = self.left.max()
            self.value = value
            self.left = self.left.remove(value)
            return self
        elif self.left:
            return self.left
        elif self.right:
            return self.right
        else:
            return None

    def remove(self, value):
        if value == self.value:
            self = self.__removenode()
        elif value < self.value:
            self.left = self.left.remove(value)
        elif value > self.value:
            self.right = self.right.remove(value)
        if self:
            self.rebuild()
        return self


def main():
    N, Q = map(int, input().split())
    construction = [None] * N
    events = [None] * (N*2+Q)
    for i in range(N):
        S, T, X = map(int, input().split())
        events[i*2] = (S-X, 1, X)
        events[i*2+1] = (T-X, 0, X)
    for i in range(Q):
        D = int(input())
        events[N*2+i] = (D, 2, 0)
    events.sort()
    bt = BinTree()
    for t, e, x in events:
        if e == 0:
            bt.remove(x)
        elif e == 1:
            bt.insert(x)
        else:
            ans = bt.min()
            if ans is None:
                print(-1)
            else:
                print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

N,Q=map(int, sys.stdin.readline().split())

S=[]
hq=[]	#x, xが答えになる開始時間, xが答えになる終了時間
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( hq, (x, max(0,s-x) , max(0,t-1-x)) )

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
D.sort()
ANS=[ float("inf") for _ in range(Q) ]

while hq:
	x,s,t=heappop(hq)

	start=bisect_left(D,s)
	end=bisect_right(D,t)

	for i in range(start,end):
		ANS[i]=min(ANS[i],x)


for x in ANS:
	if x==float("inf"):
		print -1
	else:
		print x

Submission status: Time Limit Exceeded

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

N,Q=map(int, sys.stdin.readline().split())

S=[]
hq=[]	#x, xが答えになる開始時間, xが答えになる終了時間
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	heappush( hq, (x, max(0,s-x) , max(0,t-1-x)) )

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]
ANS=[ float("inf") for _ in range(Q) ]

while hq:
	x,s,t=heappop(hq)

	start=bisect_left(D,s)
	end=bisect_right(D,t)

	for i in range(start,end):
		ANS[i]=min(ANS[i],x)


for x in ANS:
	if x==float("inf"):
		print -1
	else:
		print x

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    
    for i in range(left, right):
        if ans[i] == -1:
            ans[i] = x

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1 for _ in range(Q)]
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    
    for i in range(left, right):
        if ans[i] == -1:
            ans[i] = x

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

input = sys.stdin.readline

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1 for _ in range(Q)]
for stx in STX:
    s, t, x = stx
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    
    for i in range(left, right):
        if ans[i] == -1:
            ans[i] = x

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])

D = [int(input()) for _ in range(Q)]
ans = [-1 for _ in range(Q)]
for stx in STX:
    s, t, x = stx
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    
    for i in range(left, right):
        if ans[i] == -1:
            ans[i] = x

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())

S=[0]*N
T=[0]*N
X=[0]*N
for i in range(N):
   S[i],T[i],X[i] = map(int, input().split())

D=[0]*Q
for i in range(Q):
  D[i] = int(input())

for i in range(Q):
  R = 10**9
  for j in range(N):
     if S[j] <= D[i]+X[j] and  D[i]+X[j] < T[j]:
        R = min(R, X[j])
        continue;
  print(-1 if R==10**9 else R)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())

S=[0]*N
T=[0]*N
X=[0]*N
for i in range(N):
   S[i],T[i],X[i] = map(int, input().split())

k = zip(X,S,T)
q = sorted(k)

D=[0]*Q
for i in range(Q):
  D[i] = int(input())

for i in range(Q):
  R = -1
  for x,s,t in q:
     if s <= D[i]+x and  D[i]+x < t:
        R = x
        break;
  print(R)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = []
T = []
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    S.append(s)
    T.append(t)
    X.append(x)

D = []
for _ in range(Q):
    D.append(int(input()))

# 出発時間が区間[S -X, T - X)にあれば工事に引っかかる
W = [(S[i] - X[i], T[i] - X[i]) for i in range(N)]

for q in range(Q):
    ans = []
    for i, (s, t) in enumerate(W):
        if D[q] >= s and D[q] < t:
            ans.append(X[i])
    if len(ans) == 0:
        print(-1)
    else:
        print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

class Construction:
    def __init__(self, start, end, pos):
        self.start = start
        self.end = end
        self.pos = pos
        self.start_pos = start - pos
        self.end_pos = end - pos

class Constructions:
    def __init__(self):
        self.list = []

    def append(self, construction):
        self.list.append(construction)
    
    def sort(self):
        self.list = sorted(self.list, key=lambda x:x.start_pos)
    
    def encounter(self, p_pos):
        li = [c.pos for c in self.list if c.start_pos <= p_pos and p_pos < c.end_pos]
        if len(li) > 0:
            return min(li)
        else:
            return -1
                
    def __str__(self):
        return str([(c.start_pos, c.end_pos) for c in self.list])

class Person:
    def __init__(self, departure):
        self.departure = departure
    
class Persons:
    def __init__(self):
        self.list = []
    
    def append(self, person):
        self.list.append(person)

constructions = Constructions()
construction_num, person_num = map(int, input().split())
for i in range(construction_num):
      start, end, pos = map(int, input().split())
      c = Construction(start, end, pos)
      constructions.append(c)

persons = Persons()
for i in range(person_num):
    departure = int(input())
    p = Person(departure)
    persons.append(p)

constructions.sort()

for p in persons.list:
    print(constructions.encounter(p.departure))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
import sys
def input(): return sys.stdin.readline().strip()
STX=[list(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
X=[]
for s,t,x in STX:
    X.append((s-x,1,x))
    X.append((t-x,-1,x))
X.sort(key=lambda x:x[0])
a=0
k=[]
for x in X:
    while a<Q and D[a]<x[0]:
        if len(k)>0:
            print(min(k))
        else:
            print(-1)
        a+=1
    if x[1]==1:
        k.append(x[2])
    else:
        k.remove(x[2])
while a<Q:
    print(-1)
    a+=1

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
import sys
def input(): return sys.stdin.readline().strip()
STX=[list(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
X=[]
for s,t,x in STX:
    X.append((s-x,1,x))
    X.append((t-x,-1,x))
X.sort(key=lambda x:x[0])
a=0
k=[]
from bisect import bisect_left
for x in X:
    while a<Q and D[a]<x[0]:
        if len(k)>0:
            print(k[0])
        else:
            print(-1)
        a+=1
    if x[1]==1:
        i=bisect_left(k,x[2])
        k.insert(i,x[2])
    else:
        i=bisect_left(k,x[2])
        del k[i]
while a<Q:
    print(-1)
    a+=1

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
import sys
def input(): return sys.stdin.readline().strip()
STX=[list(map(int,input().split())) for i in range(N)]
D=[(int(input()),i) for i in range(Q)]
X=sorted([(s-x,t-x,x) for s,t,x in STX],key=lambda x:(x[2],x[0]))
from bisect import bisect
a=[-1]*Q
for x in X:
    s=bisect(D,(x[0],-1))
    e=bisect(D,(x[1],-1))
    if s!=e:
        for i in range(s,e):
            a[D[i][1]]=x[2]
        D=D[:s]+D[e:]
for l in a:
    print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

input = sys.stdin.readline

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

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

STX_array = sorted(STX_array, key=lambda x: x[2])

Q_array = [int(input()) for _ in range(Q)]

index_array = [i for i in range(Q)]

ans_array = [-1] * Q
for STX in STX_array:
    s, t, x = STX
    index_left = bisect.bisect_left(Q_array, s - 0.5 - x)
    index_right = bisect.bisect_left(Q_array, t - 0.5 - x)
    if index_left != index_right:
        for i in index_array[index_left:index_right]:
            ans_array[i] = x

        del Q_array[index_left:index_right]
        del index_array[index_left:index_right]
    if len(Q_array) == 0:
        break
for ans in ans_array:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

input = sys.stdin.readline

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

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

STX_array = sorted(STX_array, key=lambda x: x[2])

Q_array = [int(input()) for _ in range(Q)]

Q_dic = {q: i for i, q in enumerate(Q_array)}

ans_array = [-1] * Q
for STX in STX_array:
    s, t, x = STX
    index_left = bisect.bisect_left(Q_array, s - 0.5 - x)
    index_right = bisect.bisect_left(Q_array, t - 0.5 - x)
    if index_left != index_right:
        influence = Q_array[index_left:index_right]
        for i in influence:
            ans_array[Q_dic[i]] = x
        del Q_array[index_left:index_right]

for ans in ans_array:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import heapq as h
    n,q = map(int, input().split())
    tl = []
    que = []
    d = dict()
    for _ in range(n):
        s,t,x = map(int, input().split())
        h.heappush(tl,[s-x,1,x])
        h.heappush(tl,[t-x,0,x])
    for _ in range(q):
        t = int(input())
        que.append(t)
        h.heappush(tl,[t,2])
    wor = dict()
    wcur = 0
    cur = -1
    for _ in range(n*2+q):
        x = h.heappop(tl)
        if x[1] == 1:
            wcur += 1
            wor[x[2]] = 1
            if cur < 0 or x[2] < cur:
                cur = x[2]
        elif x[1] == 0:
            wcur -= 1 
            wor[x[2]] = 0
            if cur == x[2]:
                if wcur:
                    cur = min([x for x in wor if wor[x]])
                else:
                    cur = -1
        else:
            d[x[0]] = cur
    for i in que:
        print(d[i])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq as h
n,q = map(int, input().split())
tl = []
que = []
d = dict()
for _ in range(n):
  s,t,x = map(int, input().split())
  h.heappush(tl,[s-x,1,x])
  h.heappush(tl,[t-x,0,x])
for _ in range(q):
  t = int(input())
  que.append(t)
  h.heappush(tl,[t,2])
wor = dict()
wcur = 0
cur = -1
for _ in range(n*2+q):
  x = h.heappop(tl)
  if x[1] == 1:
    wcur += 1
    wor[x[2]] = 1
    if cur < 0 or x[2] < cur:
      cur = x[2]
  elif x[1] == 0:
    wcur -= 1 
    wor[x[2]] = 0
    if cur == x[2]:
      if wcur:
        cur = min([x for x in wor if wor[x]])
      else:
        cur = -1
  else:
    d[x[0]] = cur
for i in que:
  print(d[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  stxappend = stx.append
  dsappend = ds.append
  for i in range(n):
      stxappend(LI())
  for i in range(q):
      dsappend(II())
  stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      i1 = bisect.bisect_left(ds, s - x)
      i2 = bisect.bisect_left(ds, t - x)
      while i1 < i2:
          if ans[i1] == -1:
              ans[i1] = x
          i1 += 1
  print(*ans, sep='\n')
 
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  stxappend = stx.append
  dsappend = ds.append
  for i in range(n):
      stxappend(LI())
  for i in range(q):
      dsappend(II())
  stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      i1 = bisect.bisect_left(ds, s - x)
      i2 = bisect.bisect_left(ds, t - x)
      for i in range(i1, i2):
          if ans[i] == -1:
              ans[i] = x
  print(*ans, sep='\n')
 
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1]*q
  stxappend = stx.append
  dsappend = ds.append
  for i in range(n):
      stxappend(LI())
  for i in range(q):
      dsappend(II())
  # stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      i1 = bisect.bisect_left(ds, s - x)
      i2 = bisect.bisect_left(ds, t - x)
      for i in range(i1, i2):
          if (ans[i] == -1) or (ans[i] > x):
              ans[i] = x
  print(*ans, sep='\n')
 
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  stxappend = stx.append
  dsappend = ds.append
  for i in range(n):
      stxappend(LI())
  for i in range(q):
      dsappend(II())
  # stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      i1 = bisect.bisect_left(ds, s - x)
      i2 = bisect.bisect_left(ds, t - x)
      for i in range(i1, i2):
          if (ans[i] == -1) or (ans[i] > x):
              ans[i] = x
  print(*ans, sep='\n')
 
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  stxappend = stx.append
  dsappend = ds.append
  for i in range(n):
      stxappend(LI())
  for i in range(q):
      dsappend(II())
  stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      sx = s - x
      tx = t - x
      i1 = bisect.bisect_left(ds, sx)
      i2 = bisect.bisect_left(ds, tx)
      for i in range(i1, i2):
          if (ans[i] == -1) or (ans[i] > x):
              ans[i] = x
  for i in ans:
      print(i)
 
if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  stxappend = stx.append
  dsappend = ds.append
  for i in range(n):
      stxappend(LI())
  for i in range(q):
      dsappend(II())
  # stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      sx = s - x
      tx = t - x
      i1 = bisect.bisect_left(ds, sx)
      i2 = bisect.bisect_left(ds, tx)
      for i in range(i1, i2):
          if (ans[i] == -1) or (ans[i] > x):
              ans[i] = x
  for i in ans:
      print(i)
 
if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  for i in range(n):
      stx.append(LI())
  for i in range(q):
      ds.append(SI())
  # stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      sx = s - x
      tx = t - x
      i1 = bisect.bisect_left(ds, sx)
      i2 = bisect.bisect_left(ds, tx)
      for i in range(i1, i2):
          if (ans[i] == -1) or (ans[i] > x):
              ans[i] = x
  for i in ans:
      print(i)
 
if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  for i in range(n):
      stx.append(LI())
  for i in range(q):
      ds.append(II())
  # stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      sx = s - x
      tx = t - x
      i1 = bisect.bisect_left(ds, sx)
      i2 = bisect.bisect_left(ds, tx)
      for i in range(i1, i2):
          if (ans[i] == -1) or (ans[i] > x):
              ans[i] = x
  for i in ans:
      print(i)
 
if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict
import bisect

def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  for i in range(n):
      stx.append(LI())
  for i in range(q):
      ds.append(SI())
  # stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      sx = s - x
      tx = t - x
      i1 = bisect.bisect_left(ds, sx)
      i2 = bisect.bisect_left(ds, tx)
      for i in range(i1, i2):
          if (ans[i] == -1) or (ans[i] > x):
              ans[i] = x
  for i in ans:
      print(i)

if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N,Q = map(int, input().split())
STX = []
for i in range(N):
  *stx, = list(map(int, input().split()))
  STX.append(stx)
D = []
for i in range(Q):
  D.append(int(input()))

STX = sorted(STX, key=lambda x: x[2])

mask = [-1]*Q
ANS = [-1]*Q

for (s,t,x) in STX:
  s2 = (s - x)
  t2 = (t - x)

  start = bisect_left(D, s2)
  end = bisect_left(D, t2, lo=start)

  #print(start, end, DI)
  while (start < end):
    if (-1 == mask[start]):
      ANS[start] = x
      mask[start] = end
      start += 1
    else:
      start = mask[start]


print(*ANS, sep='\n')