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
from math import ceil
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def upsqrt(x):
    k = x ** 0.5
    res = 1
    while res < k:
        res <<= 1
    return res


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // ceil(self.universe_size ** 0.5)
    
    def __low(self, x):
        return x % ceil(self.universe_size ** 0.5)
    
    def __generate_index(self, x, y):
        return x * ceil(self.universe_size ** 0.5) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.__empinsert(key)
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(ceil(self.universe_size ** 0.5))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(upsqrt(self.universe_size))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    ans = []
    veb = VanEmdeBoasTree(10 ** 9)
    for _, com, pos in events:
        if com == 0:
            veb.delete(pos)
        elif com == 1:
            veb.insert(pos)
        else:
            ans.append(veb.min())
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def upsqrt(x):
    k = x ** 0.5
    res = 1
    while res < k:
        res <<= 1
    return res


def botsqrt(x):
    k = x ** 0.5
    res = 1
    while res <= k:
        res <<= 1
    return res >> 1


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // botsqrt(self.universe_size)
    
    def __low(self, x):
        return x % botsqrt(self.universe_size)
    
    def __generate_index(self, x, y):
        return x * botsqrt(self.universe_size) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.__empinsert(key)
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(botsqrt(self.universe_size))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(upsqrt(self.universe_size))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, Q = map(int, rl().split())
    events = []
    X = set()
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
        X.add(x)
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    X = tuple(sorted(X))
    x_to_idx = {x: idx for idx, x in enumerate(X)}
    
    ans = []
    veb = VanEmdeBoasTree(len(X))
    for _, com, pos in events:
        if com == 0:
            veb.delete(x_to_idx[pos])
        elif com == 1:
            veb.insert(x_to_idx[pos])
        else:
            ans.append(X[veb.min()] if veb.min() != -1 else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def upsqrt(x):
    k = x ** 0.5
    res = 1
    while res < k:
        res <<= 1
    return res


def botsqrt(x):
    k = x ** 0.5
    res = 1
    while res <= k:
        res <<= 1
    return res >> 1


class VanEmdeBoasTree:
    def __init__(self, size):
        self.universe_size = 1
        while self.universe_size < size:
            self.universe_size <<= 1
        self.minimum = -1
        self.maximum = -1
        self.summary = None
        self.cluster = {}
    
    def __high(self, x):
        return x // botsqrt(self.universe_size)
    
    def __low(self, x):
        return x % botsqrt(self.universe_size)
    
    def __generate_index(self, x, y):
        return x * botsqrt(self.universe_size) + y
    
    def min(self):
        return self.minimum
    
    def max(self):
        return self.maximum
    
    def __empinsert(self, key):
        self.minimum = self.maximum = key
    
    def insert(self, key):
        if self.minimum == -1:
            self.__empinsert(key)
        else:
            if key < self.minimum:
                self.minimum, key = key, self.minimum
            if 2 < self.universe_size:
                if self.__high(key) not in self.cluster:
                    self.cluster[self.__high(key)] = VanEmdeBoasTree(botsqrt(self.universe_size))
                    if self.summary is None:
                        self.summary = VanEmdeBoasTree(upsqrt(self.universe_size))
                    self.summary.insert(self.__high(key))
                    self.cluster[self.__high(key)].__empinsert(self.__low(key))
                else:
                    self.cluster[self.__high(key)].insert(self.__low(key))
            if self.maximum < key:
                self.maximum = key
    
    def is_member(self, key):
        if self.minimum == key or self.maximum == key:
            return True
        elif self.universe_size == 2:
            return False
        else:
            if self.__high(key) in self.cluster:
                return self.cluster[self.__high(key)].is_member(self.__low(key))
            else:
                return False
    
    def successor(self, key):
        # バグらせてるっぽい
        if self.universe_size == 2:
            if key == 0 and self.maximum == 1:
                return 1
            else:
                return -1
        elif self.minimum != -1 and key < self.minimum:
            return self.minimum
        else:
            max_incluster = -1
            if self.__high(key) in self.cluster:
                max_incluster = self.cluster[self.__high(key)].max()
            if max_incluster != -1 and self.__low(key) < max_incluster:
                offset = self.cluster[self.__high(key)].successor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                succ_cluster = -1
                if self.summary.successor is not None:
                    succ_cluster = self.summary.successor(self.__high(key))
                if succ_cluster == -1:
                    return -1
                else:
                    offset = self.cluster[succ_cluster].min()
                    return self.__generate_index(succ_cluster, offset)
    
    def predecessor(self, key):
        if self.universe_size == 2:
            if key == 1 and self.minimum == 0:
                return 0
            else:
                return -1
        elif self.maximum != -1 and self.maximum < key:
            return self.maximum
        else:
            min_incluster = -1
            if self.__high(key) in self.cluster:
                min_incluster = self.cluster[self.__high(key)].min()
            if min_incluster != -1 and min_incluster < self.__low(key):
                offset = self.cluster[self.__high(key)].predecessor(self.__low(key))
                return self.__generate_index(self.__high(key), offset)
            else:
                pred_cluster = -1
                if self.summary is not None:
                    pred_cluster = self.summary.predecessor(self.__high(key))
                if pred_cluster == -1:
                    if self.minimum != -1 and self.minimum < key:
                        return self.minimum
                    else:
                        return -1
                else:
                    offset = self.cluster[pred_cluster].max()
                    return self.__generate_index(pred_cluster, offset)
    
    def delete(self, key):
        if self.minimum == self.maximum:
            self.minimum = self.maximum = -1
            return True
        elif self.universe_size == 2:
            if key == 0:
                self.minimum = 1
            else:
                self.minimum = 0
            self.maximum = self.minimum
            return False
        else:
            if key == self.minimum:
                first_cluster = self.summary.min()
                key = self.__generate_index(first_cluster, self.cluster[first_cluster].min())
                self.minimum = key
            flg0 = self.cluster[self.__high(key)].delete(self.__low(key))
            if flg0:
                del self.cluster[self.__high(key)]
                flg1 = self.summary.delete(self.__high(key))
                if key == self.maximum:
                    if flg1:
                        self.maximum = self.minimum
                    else:
                        max_insummary = self.summary.max()
                        self.maximum = self.__generate_index(max_insummary, self.cluster[max_insummary].max())
            elif key == self.maximum:
                self.maximum = self.__generate_index(self.__high(key), self.cluster[self.__high(key)].max())


def solve():
    N, Q = map(int, rl().split())
    events = []
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    ans = []
    veb = VanEmdeBoasTree(10 ** 9)
    for _, com, pos in events:
        if com == 0:
            veb.delete(pos)
        elif com == 1:
            veb.insert(pos)
        else:
            ans.append(veb.min())
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append((max(0,s-x), max(0,t-x), x))
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+10)
STX.sort(key=lambda x:x[2])
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    for i in range(s1, t1):
        if mapping[i]==-1:
            mapping[i] = x
    
for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append([max(0,s-x), max(0,t-x), x])
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

import heapq
cur = -1
cur_priority = 10**9
que = [[cur_priority, cur]]
valid_priority = [True]*(N+1)
for i in range(L+1):
    for f,p,x in  imos[i]:
        if f:
            heapq.heappush(que, [p, x])
        else:
            valid_priority[p] = False
    
    while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
        heapq.heappop(que)
    mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append([max(0,s-x), max(0,t-x), x])
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

import heapq
cur = -1
cur_priority = 10**9
que = [[cur_priority, cur]]
valid_priority = [True]*(N+1)
for i in range(L+1):
    for f,p,x in  imos[i]:
        if f:
            heapq.heappush(que, [p, x])
        else:
            valid_priority[p] = False
    idx = 0
    while que[idx][0]!=10**9 and valid_priority[que[idx][0]]==False:
        heapq.heappop(que)
    mapping[i] = que[0][1]



        
for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append([max(0,s-x), max(0,t-x), x])
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+10)
STX.sort(key=lambda x:x[2])
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    for i in range(s1, t1):
        if mapping[i]==-1:
            mapping[i] = x
    
for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])

Submission status: Time Limit Exceeded

Solution code:
# Solution using a heapq

from heapq import heappop, heappush

n, q = map(int, input().split())
Works = [tuple(map(int, input().split())) for _ in range(n)]
People = [int(input()) for _ in range(q)]

Events = []
for i, w in enumerate(Works):
    heappush(Events, (w[0]-w[2], 0, w[2], i))
    heappush(Events, (w[1]-w[2], 1, w[2], i))

for i, d in enumerate(People):
    heappush(Events, (d, 2, d, i))

ans = [-1]*q
Progress = []
Completed = set()

while Events:
    time, flag, pos, ind = heappop(Events)
    if flag == 0:
        heappush(Progress, (pos, ind))
    elif flag == 1:
        Completed.add(ind)
    else:
        while True:
            if not Progress:
                break
            x = heappop(Progress)
            if x[1] not in Completed:
                ans[ind] = x[0]
                heappush(Progress, x)
                break

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# Solution using a heapq

from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, q = map(int, input().split())
Works = [tuple(map(int, input().split())) for _ in range(n)]
People = [int(input()) for _ in range(q)]

Events = []
for i, w in enumerate(Works):
    heappush(Events, (w[0]-w[2], 0, w[2], i))
    heappush(Events, (w[1]-w[2], 1, w[2], i))

for i, d in enumerate(People):
    heappush(Events, (d, 2, d, i))

ans = [-1]*q
Progress = []
Completed = set()

while Events:
    time, flag, pos, ind = heappop(Events)
    if flag == 0:
        heappush(Progress, (pos, ind))
    elif flag == 1:
        Completed.add(ind)
    else:
        while True:
            if not Progress:
                break
            x = heappop(Progress)
            if x[1] not in Completed:
                ans[ind] = x[0]
                heappush(Progress, x)
                break

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# Solution using a heapq

from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, q = map(int, input().split())
Works = [tuple(map(int, input().split())) for _ in range(n)]
People = [int(input()) for _ in range(q)]

Events = []
for i, w in enumerate(Works):
    heappush(Events, (w[0]-w[2], 0, w[2], i))
    heappush(Events, (w[1]-w[2], 1, w[2], i))

for i, d in enumerate(People):
    heappush(Events, (d, 2, d, i))

ans = [-1]*q
Progress = []
Completed = [False]*n

while Events:
    time, flag, pos, ind = heappop(Events)
    if flag == 0:
        heappush(Progress, (pos, ind))
    elif flag == 1:
        Completed[ind] = True
    else:
        while True:
            if not Progress:
                break
            x = heappop(Progress)
            if not Completed[x[1]]:
                ans[ind] = x[0]
                heappush(Progress, x)
                break

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# Solution using a heapq

from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, q = map(int, input().split())
Works = []
for _ in range(n):
    s, t, x = map(int, input().split())
    Works.append((s, t, x))

People = []
for _ in range(q):
    d = int(input())
    People.append(d)

Events = []
for i, (s, t, x) in enumerate(Works):
    heappush(Events, (s-x, 0, (x, i)))
    heappush(Events, (t-x, 1, (x, i)))

for i, d in enumerate(People):
    heappush(Events, (d, 2, i))

ans = [-1]*q
Progress = []
Completed = [False]*n

while Events:
    time, flag, pos = heappop(Events)
    if flag == 0:
        heappush(Progress, pos)
    elif flag == 1:
        Completed[pos[1]] = True
    else:
        while True:
            if not Progress:
                break
            x = heappop(Progress)
            if not Completed[x[1]]:
                ans[pos] = x[0]
                heappush(Progress, x)
                break

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# Solution using a heapq

from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, q = map(int, input().split())
Works = [tuple(map(int, input().split())) for _ in range(n)]
People = [int(input()) for _ in range(q)]

Events = []
for i, (s, t, x) in enumerate(Works):
    heappush(Events, (s-x, 0, (x, i)))
    heappush(Events, (t-x, 1, (x, i)))

for i, d in enumerate(People):
    heappush(Events, (d, 2, i))

ans = [-1]*q
Progress = []
Completed = [False]*n

while Events:
    time, flag, pos = heappop(Events)
    if flag == 0:
        heappush(Progress, pos)
    elif flag == 1:
        Completed[pos[1]] = True
    else:
        while True:
            if not Progress:
                break
            x = heappop(Progress)
            if not Completed[x[1]]:
                ans[pos] = x[0]
                heappush(Progress, x)
                break

for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# Solution using a heapq

from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, q = map(int, input().split())
Works = [tuple(map(int, input().split())) for _ in range(n)]
People = [int(input()) for _ in range(q)]

Events = []
for i, (s, t, x) in enumerate(Works):
    heappush(Events, (s-x, 1, (x, i)))
    heappush(Events, (t-x, 0, (x, i)))

for i, d in enumerate(People):
    heappush(Events, (d, 2, i))

ans = [-1]*q
Progress = []
Completed = [False]*n

while Events:
    time, flag, pos = heappop(Events)
    if flag == 1:
        heappush(Progress, pos)
    elif flag == 0:
        Completed[pos[1]] = True
    else:
        while True:
            if not Progress:
                break
            x = heappop(Progress)
            if not Completed[x[1]]:
                ans[pos] = x[0]
                heappush(Progress, x)
                break

for x in ans:
    print(x)