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: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,Q = LI()
    e = []
    for i in range(n):
        s,t,x = LI()
        e.append((s-x,x,1))
        e.append((t-x,x,0))
    e.sort(key = lambda x : x[0])
    m = 2*n
    q = set()
    j = 0
    ans = float("inf")
    for i in range(Q):
        d = I()
        while j < m:
            t,x,k = e[j]
            if d < t:
                break
            if k:
                q.add(x)
                if x < ans:
                    ans = x
            else:
                q.remove(x)
                if ans == x:
                    if len(q):
                        ans = min(q)
                    else:
                        ans = float("inf")
            j += 1
        print(-1 if ans == float("inf") else ans)
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,Q = LI()
    e = []
    for i in range(n):
        s,t,x = LI()
        e.append([s-x,x,1])
        e.append([t-x,x,0])
    e.sort(key = lambda x : x[0])
    m = 2*n
    q = set()
    j = 0
    ans = float("inf")
    for i in range(Q):
        d = I()
        while j < m:
            t,x,k = e[j]
            if d < t:
                break
            if k:
                q.add(x)
                if x < ans:
                    ans = x
            else:
                q.remove(x)
                if ans == x:
                    if q:
                        ans = min(q)
                    else:
                        ans = float("inf")
            j += 1
        print(-1 if ans == float("inf") else ans)
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return

#D
def D():
    n,k = LI()
    v = LI()
    ans = -float("inf")
    for l in range(min(k,n)+1):
        for r in range(min(k,n)-l+1):
            m = 0
            q = v[:l]+v[n-r:]
            q.sort()
            res = max(0,k-r-l)
            for i in range(len(q)):
                if q[i] < 0 and res > 0:
                    res -= 1
                else:
                    m += q[i]
            if m > ans:
                ans = m
    print(ans)
    return

#E
def E():
    n,Q = LI()
    e = []
    for i in range(n):
        s,t,x = LI()
        e.append((s-x,x,1))
        e.append((t-x,x,0))
    e.sort(key = lambda x:x[0])
    m = 2*n
    q = set()
    j = 0
    ans = float("inf")
    for i in range(Q):
        d = I()
        while j < m:
            t,x,k = e[j]
            if d < t:
                break
            if k:
                q.add(x)
                if x < ans:
                    ans = x
            else:
                q.remove(x)
                if ans == x:
                    if q:
                        ans = min(q)
                    else:
                        ans = float("inf")
            j += 1
        if q:
            print(ans)
        else:
            print(-1)
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
 
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
index = [-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)
    now = left
    while now < right:
        if index[now] == -1:  # まだansが更新されていない場合
            ans[now] = x
            index[now] = right
            now += 1
        else:
            now = index[now]
            
 
for a in ans:
    print(a)
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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
index = [-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)
    now = left
    while now < right:
        if index[now] == -1:  # まだansが更新されていない場合
            ans[now] = x
            index[now] = right
            now += 1
        else:
            now = index[now]
            
 
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


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

Submission status: Runtime Error

Solution code:
N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    STX.append(list(map(int, input().split())))
STX.sort(key=lambda x: x[0])

kensaku = dict()
for i in range(Q):
    D.append(int(input()))
    kensaku[D[-1]] = i

dist = [10000000000000 for i in range(Q)]

for i in range(N):
    s = STX[i][0] - STX[i][2]
    t = STX[i][1] - STX[i][2] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    for j in range(a, b):
        dist[kensaku[D[j]]] = min(dist[kensaku[D[j]]], STX[i][2])
    del D[a:b]


for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

# random_denseがTLE, 他はAC
def main_tle():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み

    events = []
    for s, t, x in STX:
        events.append(('S', (s-x-0.5), x))
        events.append(('T', (t-x-0.5), x))
    for i, d in enumerate(D):
        events.append(('D', d, i))
    
    ans = [-1] * Q
    events.sort(key=lambda v: v[1])
    xset = set()
    xmin = None
    for event, time, xi in events:
        if event == 'S':
            xset.add(xi)
            if xmin is None or xmin > xi:
                xmin = xi
        elif event == 'T':
            xi = xi
            xset.remove(xi)
            if xmin == xi:
                xmin = None
        elif event == 'D' and xset:
            if xmin is None:
                xmin = min(xset)
            ans[xi] = xmin

    for n in ans:
        print(n)

main()

Submission status: Runtime Error

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

# random_denseがTLE, 他はAC
def main_tle():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み

    events = []
    for s, t, x in STX:
        events.append(('S', (s-x-0.5), x))
        events.append(('T', (t-x-0.5), x))
    for i, d in enumerate(D):
        events.append(('D', d, i))
    
    ans = [-1] * Q
    events.sort(key=lambda v: v[1])
    xset = set()
    xmin = None
    for event, time, xi in events:
        if event == 'S':
            x = xi
            xset.add(x)
            if xmin is None or xmin > x:
                xmin = x
        elif event == 'T':
            x = xi
            xset.remove(x)
            if xmin == x:
                xmin = None
        else:
            i = xi
            if not xset:
                continue
            if xmin is None:
                xmin = min(xset)
            ans[i] = xmin

    for n in ans:
        print(n)

main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
event=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	event.append(  ( s-x ,1, x) )	#Start
	event.append(  ( t-x,-1, x) )	#End


for i in range(Q):
	d=int(sys.stdin.readline().strip())
	event.append(  (d ,0, i) )

event.sort(key=lambda x:(x[0]) )

stop=set()

ans=defaultdict(lambda: -1) 

for s,flag,x in event:
	if flag==1:
		stop.add(x)
	elif flag==-1:
		stop.remove(x)
	elif flag==0:
		if stop:
			ans[x]=min(stop)
		else:
			ans[x]=-1


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

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
stx=[]
m=0
for i in range(n):
    p=[int(j) for j in input().split()]
    stx.append([max(p[0]-p[2],0),p[1]-p[2]-1,p[2]])
    m=max(m,p[1]-p[2])
from operator import itemgetter
stx.sort(key=itemgetter(2))
stx=stx[::-1]
l=[-1]*(m+7)
for i in range(n):
    l[stx[i][0]:stx[i][1]+1]=[stx[i][2]]*(stx[i][1]-stx[i][0]+1)
d=[]
for i in range(q):
    d.append(int(input()))

for i in d:
    print(l[i])

Submission status: Runtime Error

Solution code:
# coding: utf-8

class Construction:
    def __init__(self, start, end, pos):
        self.start = start - .5
        self.end = end - .5
        self.pos = pos
        self.working = False

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

    def append(self, construction):
        self.list.append(construction)
        if self.start_max < construction.start:
            self.start_max = construction.start
    
    def sort(self):
        self.list = sorted(self.list, key=lambda x:x.start)

    def __iter__(self):
        for c in self.list:
            yield c
    
    def isEncounter(self, pos):
        for c in self.list:
            if c.working and pos == c.pos:
                return True
        return False
    
    def __str__(self):
        return str([(c.start, c.end, c.pos, c.working) for c in self.list])

    def step(self, elapsed_time):
        for c in self.list:
            if c.start <= elapsed_time and c.end >= elapsed_time:
                c.working = True
            else:
                c.working = False

class Person:
    def __init__(self, departure):
        self.departure = departure
        self.pos = 0
        self.walking = True
    
    def walk(self):
        if self.walking:
            self.pos += 1
    
    def stop(self):
        self.walking = False

class Persons:
    def __init__(self):
        self.list = []
        self.departure_max= 0

    def append(self, person):
        self.list.append(person)
        if self.departure_max < person.departure:
            self.departure_max = person.departure

    def __iter__(self):
        for p in self.list:
            yield p

    def __str__(self):
        return str([(p.departure, p.pos) for p in self.list])

input_line = input()
construction_num, person_num = map(int, input_line.split())      

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

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

constructions.sort()

elapsed_time = 0
while True:
    for index, p in enumerate(persons):
        constructions.step(elapsed_time)
        if constructions.isEncounter(p.pos):
            p.stop()
        
        if p.pos > constructions.start_max:
            p.stop()
            p.pos = -1

        if p.departure <= elapsed_time:
            p.walk()

    elapsed_time += 1
    if any([p.walking for p in persons]) == False:
        break

for p in persons:
    print(p.pos)

Submission status: Runtime Error

Solution code:
 import sys
import bisect

sys.setrecursionlimit(10**8)

class SegmentTree(object):  #1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        self.default = value
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def get(self, i):
        i += self.len
        ans = self.default
        while i > 0:
            ans = min(self.array[i], ans)
            i >>= 1
        return ans

    def query(self, l, r, v, i, a, b):
        if self.array[i] != self.default:
            return 0
        if l == a and r == b:
            self.array[i] = v
            return 0
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, v, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, v, i * 2 + 1, center, b) 
        else:
            return min(
                self.query(l, center, v, i * 2, a, center),
                self.query(center, r, v, i * 2 + 1, center, b))

    def update(self, l, r, v):
        return self.query(l, r, v, 1, 0, self.len)


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)]

INF = 10**9 + 7

seg_tree = SegmentTree(Q, INF)

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:
        seg_tree.update(index_left, index_right, x)

for i in range(Q):
    ans = seg_tree.get(i)
    print(ans) if ans != INF else print(-1)

Submission status: Runtime Error

Solution code:
import sys
import bisect

sys.setrecursionlimit(10**8)

class SegmentTree(object):  #1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        self.default = value
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def get(self, i):
        i += self.len
        ans = self.default
        while i > 0:
            ans = min(self.array[i], ans)
            i >>= 1
        return ans

    def query(self, l, r, v, i, a, b):
        if self.array[i] != self.default:
            return 0
        if l == a and r == b:
            self.array[i] = v
            return 0
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, v, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, v, i * 2 + 1, center, b) 
        else:
            return min(
                self.query(l, center, v, i * 2, a, center),
                self.query(center, r, v, i * 2 + 1, center, b))

    def update(self, l, r, v):
        return self.query(l, r, v, 1, 0, self.len)


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)]

INF = 10**9 + 7

seg_tree = SegmentTree(Q, INF)

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)
    seg_tree.update(index_left, index_right, x)

for i in range(Q):
    ans = seg_tree.get(i)
    print(ans) if ans != INF else print(-1)

Submission status: Runtime Error

Solution code:
import sys
import bisect


class SegmentTree(object):  #1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        self.default = value
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def get(self, i):
        i += self.len
        ans = self.default
        while i > 0:
            ans = min(self.array[i], ans)
            i >>= 1
        return ans

    def query(self, l, r, v, i, a, b):
        if self.array[i] != self.default:
            return 0
        if l == a and r == b:
            self.array[i] = v
            return 0
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, v, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, v, i * 2 + 1, center, b) 
        else:
            return min(
                self.query(l, center, v, i * 2, a, center),
                self.query(center, r, v, i * 2 + 1, center, b))

    def update(self, l, r, v):
        return self.query(l, r, v, 1, 0, self.len)


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)]

INF = 10**9 + 7

seg_tree = SegmentTree(Q, INF)

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)
    seg_tree.update(index_left, index_right, x)

for i in range(Q):
    ans = seg_tree.get(i)
    print(ans) if ans != INF else print(-1)

Submission status: Runtime Error

Solution code:
import sys
import bisect


class SegmentTree(object):  #1-indexed
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        self.default = value
        print(self.len)
        self.array = [value] * (2 * self.len)

    def get(self, i):
        i += self.len
        ans = self.default
        while i > 0:
            ans = min(self.array[i], ans)
            i >>= 1
        return ans

    def query(self, l, r, v, i, a, b):
        if self.array[i] != self.default:
            return 0
        if l == a and r == b:
            self.array[i] = v
            return 0
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, v, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, v, i * 2 + 1, center, b) 
        else:
            return min(
                self.query(l, center, v, i * 2, a, center),
                self.query(center, r, v, i * 2 + 1, center, b))

    def update(self, l, r, v):
        return self.query(l, r, v, 1, 0, self.len)


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)]

INF = 10**9 + 7

seg_tree = SegmentTree(Q, INF)

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)
    seg_tree.update(index_left, index_right, x)

for i in range(Q):
    ans = seg_tree.get(i)
    print(ans) if ans != INF else print(-1)

Submission status: Runtime Error

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 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: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(query[-1]+1)

   # for s, t, x in works:
   #     start = s-x if s-x >= 0 else 0
   #     end = t-x if t-x >= 0 else 0
   #     for p in range(start, min(end, len(L))):
  #          L[p] = x
 # for q in query:

    print(0)


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(max(query)+1)

   # for s, t, x in works:
   #     start = s-x if s-x >= 0 else 0
   #     end = t-x if t-x >= 0 else 0
   #     for p in range(start, min(end, len(L))):
  #          L[p] = x
 # for q in query:
    print(0)


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(max(query)+1)

   # for s, t, x in works:
   #     start = s-x if s-x >= 0 else 0
   #     end = t-x if t-x >= 0 else 0
   #     for p in range(start, min(end, len(L))):
  #          L[p] = x
    for q in query:
        print(L[0])


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(max(query)+1)

    for s, t, x in works:
        start = s-x if s-x >= 0 else 0
        end = t-x if t-x >= 0 else 0
        for p in range(start, min(end, len(L))):
            L[p] = x
    for q in query:
        print(L[0])


solve()