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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n_consts, n_agents = map(int, input().split())
const_plans = []
dep_times = []
results = [-1 for _ in range(n_agents)]

for _ in range(n_consts):
    const_plans.append([int(e) for e in input().split()])

const_plans = np.array(const_plans)
order_by_x = np.argsort(const_plans.T)[-1]
const_plans = const_plans[order_by_x]

for _ in range(n_agents):
    dep_times.append(int(input()))

for n_agent, dep_time in enumerate(dep_times):
    for const_plan in const_plans:
        x = const_plan[2]
        x1 = max(0, const_plan[0] - dep_time)
        x2 = max(0, const_plan[1] - dep_time)
        if x1 <= x < x2:
            results[n_agent] = x
            break

for result in results:
    print(result)

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline

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

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

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

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


class DammyMap:


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

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))
        
        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]
        
    
    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

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

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

            self.bit.add(ix, -v)


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

        vals = []
        rmvs = []

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d) : vals.append(self.key[OK]*1)
            rmvs.append([OK, d])
            tv += d
            tix = OK
            delta -= d
        
        for ix, d in rmvs:
            self.bit.add(ix, -d)
        return vals


N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def get_block(const_plans, t):
    block = []
    for const_plan in const_plans:
        if const_plan[0] - 1 <= t <= const_plan[1] - 2:
            block.append(const_plan[2])
    return block

n_consts, n_agents = map(int, input().split())
const_plans = []
dep_times = []
results = [-1 for _ in range(n_agents)]

for _ in range(n_consts):
    const_plans.append([int(e) for e in input().split()])
    
for _ in range(n_agents):
    dep_times.append(int(input()))

for n_agent, dep_time in enumerate(dep_times):
    for const_plan in const_plans:
        x = const_plan[2]
        x1 = max(0, const_plan[0] - dep_time)
        x2 = max(0, const_plan[1] - dep_time)
        if x1 <= x < x2:
            print
            if results[n_agent] == -1:
                results[n_agent] = x
            else:
                results[n_agent] = min(x, results[n_agent])

for result in results:
    print(result)

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline

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

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

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

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


class DammyMap:


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

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))
        
        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]
        
    
    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

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

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

            self.bit.add(ix, -v)


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

        vals = []
        rmvs = []

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            rmvs.append([OK, d])
            tv += d
            tix = OK
            delta -= d
        
        for ix, d in rmvs:
            self.bit.add(ix, -d)
        return vals


N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.pop_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline

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

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

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

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


class DammyMap:


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

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))
        
        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]
        
    
    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

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

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

            self.bit.add(ix, -v)


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

        vals = []
        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            tv += d
            tix = OK
            delta -= d
        return vals


N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.get_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
    dmap.remove(val)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline

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

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

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

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


class DammyMap:


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

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))
        
        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]
        
    
    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

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

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

            self.bit.add(ix, -v)


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

        vals = []
        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            tv += d
            tix = OK
            delta -= d
        return vals


N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.get_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
    dmap.remove(val)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

import sys
#input = sys.stdin.readline

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

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

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

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


class DammyMap:


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

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))
        
        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]
        
    
    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

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

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

            self.bit.add(ix, -v)


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

        vals = []
        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            tv += d
            tix = OK
            delta -= d
        return vals


N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.get_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
    dmap.remove(val)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return map(int,input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return map(int, [ input() for _ in range(n)])


n,q = get_nums_l()
lines = sys.stdin.readlines()
d = deque()
event = []
for line in lines[:n]:
    s,t,x = map(int, line.split(" "))
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
#event.sort(key=lambda e:e[1])
#event.sort(key=lambda e:e[0])
event.sort()

next = 0
s = set()
i_max = len(event)
for line in lines[n:]:
    di = int(line)
    while((next < i_max) and (event[next][0] <= di) ):
        e = event[next]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        next += 1
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return map(int,input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return map(int, [ input() for _ in range(n)])


n,q = get_nums_l()
lines = sys.stdin.readlines()
d = deque()
event = []
for line in lines[:n]:
    s,t,x = map(int, line.split(" "))
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])

next = 0
s = set()
i_max = len(event)
for line in lines[n:]:
    di = int(line)
    while((next < i_max) and (event[next][0] <= di) ):
        e = event[next]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        next += 1
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return map(int,input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return map(int, [ input() for _ in range(n)])


n,q = get_nums_l()
lines = sys.stdin.readlines()

event = []
for line in lines[:n]:
    s,t,x = map(int, line.split(" "))
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort()

last = -1
s = set()
i_max = len(event)
for line in lines[n:]:
    di = int(line)
    while(((last+1) < i_max) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Time Limit Exceeded

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



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

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = bisect_left(Dn,t)
    for i in range(r-l+1):
      if Dn[l] < t:
        ans[Dn[l]] = x
        Dn.pop(l)

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

  return ans


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

Submission status: Time Limit Exceeded

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



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

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

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

  return ans


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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return map(int,input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return map(int, [ input() for _ in range(n)])


n,q = get_nums_l()
lines = sys.stdin.readlines()

event = []
for line in lines[:n]:
    s,t,x = map(int, line.split(" "))
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])

last = -1
s = set()
i_max = len(event)
for line in lines[n:]:
    di = int(line)
    while(((last+1) < i_max) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Time Limit Exceeded

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



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

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

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

  return ans


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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return map(int,input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return map(int, [ input() for _ in range(n)])

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])

last = -1
s = set()
i_max = len(event)
for _ in range(q):
    di = int(input())
    while(((last+1) < i_max) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return map(int,input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return map(int, [ input() for _ in range(n)])

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])
d = list(get_nums_n(q))

last = -1
s = set()
i_max = len(event)
for di in d:
    while(((last+1) < i_max) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return map(int,input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])
d = list(get_nums_n(q))

last = -1
s = set()
i_max = len(event)
for di in d:
    while(((last+1) < i_max) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return tuple( int(s) for s in input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])
d = list(get_nums_n(q))

last = -1
s = set()
i_max = len(event)
for di in d:
    while(((last+1) < i_max) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)