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
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))

#################

from operator import itemgetter
from bisect import bisect_left

class LazySegmentTree:
    def __init__(self,N,default=float('inf')):
        #演算の定義
        self.op = min
        #初期化の値
        self.default = default
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.default]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)

    #伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self,l,r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    #1-indexedで単調増加のインデックスリストを渡す
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.tree[2*i-1] = self.lazy[2*i] = self.tree[2*i] = v
            self.lazy[i-1] = None

    #区間[l,r)の値をxに更新
    def update(self,l,r,x):
        if l < r:
            *ids, = self.gindex(l, r)
            self.propagates(*ids)

            L = l + self.N0; R = r + self.N0
            while L < R:
                if R & 1:
                    R -= 1
                    self.lazy[R-1] = self.tree[R-1] = x
                if L & 1:
                    self.lazy[L-1] = self.tree[L-1] = x
                    L += 1
                L >>= 1; R >>= 1

            for i in ids:
                self.tree[i-1] = self.op(self.tree[2*i-1], self.tree[2*i])

    #区間[l,r)へのクエリ
    def query(self,l,r):
        self.propagates(*self.gindex(l, r))
        L = l + self.N0; R = r + self.N0
        s = self.default
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s,self.tree[R-1])
            if L & 1:
                s = self.op(s,self.tree[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

N,Q = II()
a = []
for _ in range(N):
    s,t,x = II()
    a.append((x, s-x-0.5, t-x-0.5))
D = Line(Q,1)

a.sort(key=itemgetter(0),reverse=True)

seg = LazySegmentTree(Q, 10**9+1)
for i in range(N):
    l = bisect_left(D,a[i][1]) + 1
    r = bisect_left(D,a[i][2]) + 1
    seg.update(l,r,a[i][0])

for i in range(Q):
    x = seg.query(i+1,i+2)
    if x == 10**9+1:
        print(-1)
    else:
        print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))

#################

from operator import itemgetter
from bisect import bisect_left

class LazySegmentTree:
    def __init__(self,N,default=float('inf')):
        #演算の定義
        self.op = min
        #初期化の値
        self.default = default
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.default]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)

    #伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self,l,r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    #1-indexedで単調増加のインデックスリストを渡す
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.tree[2*i-1] = self.lazy[2*i] = self.tree[2*i] = v
            self.lazy[i-1] = None

    #区間[l,r)の値をxに更新
    def update(self,l,r,x):
        if l < r:
            *ids, = self.gindex(l, r)
            self.propagates(*ids)

            L = l + self.N0; R = r + self.N0
            while L < R:
                if R & 1:
                    R -= 1
                    self.lazy[R-1] = self.tree[R-1] = x
                if L & 1:
                    self.lazy[L-1] = self.tree[L-1] = x
                    L += 1
                L >>= 1; R >>= 1

            for i in ids:
                self.tree[i-1] = self.op(self.tree[2*i-1], self.tree[2*i])

    #区間[l,r)へのクエリ
    def query(self,l,r):
        self.propagates(*self.gindex(l, r))
        L = l + self.N0; R = r + self.N0
        s = self.default
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s,self.tree[R-1])
            if L & 1:
                s = self.op(s,self.tree[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

N,Q = II()
S,T,X = Line(N,3)
D = Line(Q,1)

a = []
for i in range(N):
    a.append([X[i], S[i]-X[i]-0.5, T[i]-X[i]-0.5])
a.sort(key=itemgetter(0),reverse=True)

seg = LazySegmentTree(Q,10**9+1)
for i in range(N):
    l = bisect_left(D,a[i][1]) + 1
    r = bisect_left(D,a[i][2]) + 1
    seg.update(l,r,a[i][0])

for i in range(Q):
    x = seg.query(i+1,i+2)
    if x == 10**9+1:
        print(-1)
    else:
        print(x)

Submission status: Time Limit Exceeded

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

sList = []
tList = []
xList = []
for i in range(N):
    Si, Ti, Xi = map(int, input().split())
    sList.append(Si)
    tList.append(Ti)
    xList.append(Xi)

dList = []
for i in range(Q):
    dList.append(int(input()))

dxList = []
for i in range(Q):
    dxList.append(-1)

dList_copy = dList[:]
dOrgIndex = []
for i in range(Q):
    dOrgIndex.append(i)

for i in range(Q-1):
    Dmin = dList_copy[i]
    DminIndex = i
    for j in range(i+1, Q):
        if dList_copy[j] < Dmin:
            Dmin = dList_copy[j]
            DminIndex = j
    Di = dList_copy[i]
    dList_copy.pop(i)
    dList_copy.insert(i, Dmin)
    dList_copy.pop(DminIndex)
    dList_copy.insert(DminIndex, Di)
    dOrgI_i = dOrgIndex[i]
    dOrgI_min = dOrgIndex[DminIndex]
    dOrgIndex.pop(i)
    dOrgIndex.insert(i, dOrgI_min)
    dOrgIndex.pop(DminIndex)
    dOrgIndex.insert(DminIndex, dOrgI_i)

for i, Xi in enumerate(xList):
    constStart = sList[i] - Xi
    constStop = tList[i] - Xi - 1
    startIndex = -1
    endIndex = -1
    for j, Dj in enumerate(dList_copy):
        if Dj >= constStart:
            startIndex = j
            for k in range(j+1, Q):
                if dList_copy[k] > constStop:
                    endIndex = k-1
                    break
            break
    if startIndex != -1:
        if endIndex != -1:
            for j in range(startIndex, endIndex+1):
                dOrgI = dOrgIndex[j]
                dx = dxList[dOrgI]
                if dx == -1 or dx > Xi:
                    dxList.pop(dOrgI)
                    dxList.insert(dOrgI, Xi)
        else:
            for j in range(startIndex, Q):
                dOrgI = dOrgIndex[j]
                dx = dxList[dOrgI]
                if dx == -1 or dx > Xi:
                    dxList.pop(dOrgI)
                    dxList.insert(dOrgI, Xi)

for i, e in enumerate(dxList):
    print(e)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *
INF = float('inf')

N, Q = map(int, input().split())
event = [None] * (2*N+Q)
for i in range(N):
    s, t, x = map(int, input().split())
    event[i] = (s-x, 0, x)
    event[i+N] = (t-x, -1, x)
for i in range(Q):
    event[2*N+i] = (int(input()), 1, i)
event.sort()
h = [INF]
se = set()
se.add(INF)
ans = [-1] * Q
for t, f, x in event:
    if f == -1:
        se.remove(x)
    elif f == 0:
        se.add(x)
        heappush(h, x)
    else:
        while h[0] != INF:
            if h[0] in se:
                ans[x] = h[0]
                break
            else:
                heappop(h)
print(*ans, sep = "\n")

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
sList = []
tList = []
xList = []

for i in range(N):
    Si, Ti, Xi = map(int, input().split())
    sList.append(Si)
    tList.append(Ti)
    xList.append(Xi)

for i in range(N-1):
    minXfromi = xList[i]
    minXindex = i
    for j in range(i+1,N):
        if minXfromi > xList[j]:
            minXfromi = xList[j]
            minXindex = j
    Si = sList[i]
    Ti = tList[i]
    Xi = xList[i]
    Smin = sList[minXindex]
    Tmin = tList[minXindex]
    Xmin = xList[minXindex]
    sList.pop(i)
    sList.insert(i, Smin)
    tList.pop(i)
    tList.insert(i, Tmin)
    xList.pop(i)
    xList.insert(i, Xmin)
    sList.pop(minXindex)
    sList.insert(minXindex, Si)
    tList.pop(minXindex)
    tList.insert(minXindex, Ti)
    xList.pop(minXindex)
    xList.insert(minXindex, Xi)

constStart = []
constStop = []

for i in range(N):
    Si = sList[i]
    Ti = tList[i]
    Xi = xList[i]
    constStart.append(Si-Xi)
    constStop.append(Ti-Xi-1)

dList = []
for i in range(Q):
    dList.append(int(input()))

for i, Di in enumerate(dList):
    isConst = False
    for j in range(N):
        if constStart[j] <= Di and Di <= constStop[j]:
            isConst = True
            print(xList[j])
            break
    if not isConst:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    N, Q = map(int, input().split())
    stx = [tuple(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]

    xst = sorted((x, s, t) for s, t, x in stx)
    D1 = sorted((d, i) for i, d in enumerate(D))
    ret = [-1] * Q
    for x, s, t in reversed(xst):
        left = bisect.bisect_left(D1, (s - x, -1))
        right = bisect.bisect_left(D1, (t - x, -1))
        for j in range(left, right):
            ret[D1[j][1]] = x
    for x in ret:
        print(x)


main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    N, Q = map(int, input().split())
    stx = [tuple(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]

    xst = sorted((x, s, t) for s, t, x in stx)
    D1 = sorted((d, i) for i, d in enumerate(D))
    ret = [-1] * Q
    for x, s, t in reversed(xst):
        left = bisect.bisect_left(D1, (s - x, -1))
        right = bisect.bisect_left(D1, (t - x, -1))
        for _, i in D1[left:right]:
            ret[i] = x
    print('\n'.join(map(str, ret)))


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 26 20:56:13 2019

@author: Yamazaki Kenichi
"""
import bisect

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

stx.sort(reverse = True, key=lambda x:x[2])

color = [i+1 for i in range(Q)]
ans = [-1 for i in range(Q)]
for c in stx:
    s = c[0] - c[2]
    t = c[1] - c[2]
    stop_s = bisect.bisect_left(D,s)
    stop_e = bisect.bisect_left(D,t)
    for i in range(stop_s,stop_e):
        ans[i] = c[2]
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

event = list()
for _ in range(N):
    S, T, X = map(int, input().split())
    heappush(event, (S - X, 1, X))
    heappush(event, (T - X, -1, X))

D = [int(input()) for _ in range(Q)]
stop = set()
for d in D:
    while len(event) > 0:
        t, op, X = heappop(event)
        if t > d:
            heappush(event, (t, op, X))
            break
        if op == 1:
            stop.add(X)
        elif op == -1:
            stop.remove(X)
    ans = min(stop) if len(stop) > 0 else -1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from operator import itemgetter

N, Q = map(int, input().split())
event = []
nums = []

for i in range(N):
    s, t, x = map(int, input().split())
    event.extend([(s-x, 1, x), (t-x, -1, x)])

event = sorted(event, key=itemgetter(0))

for i in range(Q):
    d = int(input())
    
    while len(event) and event[0][0] <= d:
        e = event.pop(0)
        if e[1] == 1:
            bisect.insort_left(nums, e[2])
        else:
            del nums[bisect.bisect_left(nums, e[2])]
    
    if nums:
        print(nums[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
XST = []
for i in range(N):
  S,T,X = map(int,input().split())
  XST.append([X,S,T])
XST.sort(key=lambda x:(x[0],x[1]))
#print(XST)
D = []
for i in range(Q):
  D.append(int(input()))
#print(D)

ans = [-1] * Q
for x,s,t in XST:
  for i in range(Q):
    #print(D[i],x,s,t,ans[i])
    if ans[i] == -1:
      if s <= D[i] + x and D[i] + x < t:
        ans[i] = x
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

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

lst.sort()
#print (lst)

def check(a):
    for j in range(len(lst)):
            if lst[j][1] <= a and a < lst[j][2]:
                return lst[j][0]
            elif j == len(lst) - 1:
                return -1

for i in range(Q):
    D = int(input())
    print (check(D))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

def main():
	input = sys.stdin.readline
	N,Q = map(int, input().split())
	s = [0]*N
	t = [0]*N
	x = [0]*N
	for i in range(N):
		S,T,X = map(int, input().split())
		s[i] = S-X
		t[i] = T-X
		x[i] = X
	D = [ int(input()) for i in range(Q)]
	comp = s+t+D
	comp = list(set(comp))
	comp.sort()

	comp = {v:i for i,v in enumerate(comp)}
	decomp = {v:k for k,v in comp.items()}
	ds = { comp[v] for v in D}
	res = {}
	for S,T,X in zip(s,t,x):
		st = {i for i in range(comp[S], comp[T])}
		match = st & ds
		if len(match) == 0: continue
		[ res.setdefault(decomp[i], []).append(X) for i in match]
	[ print(min( res.get(i,[-1] ))) for i in D]

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import array


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    events = []
    event_id = 0
    for s, t, x in zip(S, T, X):
        heapq.heappush(events, (s - x, event_id, 0, x))
        heapq.heappush(events, (t - x, event_id, 1, x))
        event_id += 1

    cands = []
    disposed = array.array("b", (0 for _ in range(event_id)))
    for d in D:
        while len(events) > 0 and events[0][0] <= d:
            _, event_id, event_type, cand = heapq.heappop(events)
            if event_type == 0:
                heapq.heappush(cands, (cand, event_id))
            else:
                disposed[event_id] = 1

        while len(cands) > 0 and disposed[cands[0][1]] == 1:
            _, event_id = heapq.heappop(cands)

        if len(cands) == 0:
            print(-1)
        else:
            print(cands[0][0])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]"
    T = [int()] * (N)  # type: "List[int]"
    X = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    ans = solve(N, Q, S, T, X, D)
    if ans is not None:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
dct = {}
for i in range(n):
  a,b,c = map(int, input().split())
  tpl = (a-0.5,b-0.5)
  if c in dct:
    dct[c].append(tpl)
  else:
    dct[c] = [tpl]
max_point = max(dct.keys())
for time in range(q):
  time = int(input())
  point = 0
  end_loop = False
  while True:
    time += 1
    point += 1
    if point in dct:
      for x, y in dct[point]:
        if x < time < y:
          print(point)
          end_loop = True
          break
    if end_loop:
      break
    if point > max_point:
      print(-1)
      break

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
dct = {}
for i in range(n):
  a,b,c = map(int, input().split())
  tpl = (a-0.5,b-0.5)
  if c in dct:
    dct[c].append(tpl)
  else:
    dct[c] = [tpl]
arr2 = []
for i in range(q):
  arr2.append(int(input()))
max_point = max(dct.keys())
all_stopping_points = dct.keys()
for time in arr2:
  point = 0
  end_loop = False
  while True:
    time += 1
    point += 1
    if point in all_stopping_points:
      for x, y in dct[point]:
        if x < time < y:
          print(point)
          end_loop = True
          break
    if end_loop:
      break
    if point > max_point:
      print(-1)
      break

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import array


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    events = []
    event_id = 0
    for s, t, x in zip(S, T, X):
        heapq.heappush(events, (s - x, event_id, "add", x))
        heapq.heappush(events, (t - x, event_id, "remove", x))
        event_id += 1

    cands = []
    disposed = array.array("b", [0] * len(events))
    for d in D:
        while len(events) > 0 and events[0][0] <= d:
            _, event_id, event_type, cand = heapq.heappop(events)
            if event_type == "add":
                heapq.heappush(cands, (cand, event_id))
            else:
                disposed[event_id] = 1

        while len(cands) > 0 and disposed[cands[0][1]] == 1:
            _, event_id = heapq.heappop(cands)

        if len(cands) == 0:
            print(-1)
        else:
            print(cands[0][0])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]"
    T = [int()] * (N)  # type: "List[int]"
    X = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    ans = solve(N, Q, S, T, X, D)
    if ans is not None:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):
    events = []
    event_id = 0
    for s, t, x in zip(S, T, X):
        heapq.heappush(events, (s - x, event_id, "add", x))
        heapq.heappush(events, (t - x, event_id, "remove", x))
        event_id += 1

    cands = []
    disposed = set()
    for d in D:
        while len(events) > 0 and events[0][0] <= d:
            _, event_id, event_type, cand = heapq.heappop(events)
            if event_type == "add":
                heapq.heappush(cands, (cand, event_id))
            else:
                disposed.add(event_id)

        while len(cands) > 0 and cands[0][1] in disposed:
            _, event_id = heapq.heappop(cands)
            disposed.remove(event_id)

        if len(cands) == 0:
            print(-1)
        else:
            print(cands[0][0])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]"
    T = [int()] * (N)  # type: "List[int]"
    X = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    ans = solve(N, Q, S, T, X, D)
    if ans is not None:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
def main():
	N,Q = map(int, input().split())
	S = [0]*N
	T = [0]*N
	X = [0]*N
	for i in range(N):
		s, t, x = map(int, input().split())
		S[i] = s-x
		T[i] = t-x
		X[i] = x
	D = [ int(input()) for _ in range(Q)]
	comp = sorted(set(S + T + D))
	decomp = list(comp)
	comp = {v:i for i,v in enumerate(comp)}
	comp_d = { comp[v] for v in D}
	
	res = {}
	for s, t, x in zip(S,T,X):
		match = { _ for _ in range(comp[s], comp[t])} & comp_d
		[ res.setdefault(decomp[i], []).append(x) for i in match]
	[ print(min( res.get(i,[-1] ))) for i in D]

main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from operator import itemgetter

N,Q = map(int, input().split())
s = [0]*N
t = [0]*N
x = [0]*N
for i in range(N):
	S,T,X = map(int, input().split())
	s[i] = S-X
	t[i] = T-X
	x[i] = X
D = [ int(input()) for i in range(Q)]
comp = s+t+D
comp = list(set(comp))
comp.sort()

comp = {v:i for i,v in enumerate(comp)}
decomp = {v:k for k,v in comp.items()}
ds = { comp[v] for v in D}
res = {}
for S,T,X in zip(s,t,x):
	st = {i for i in range(comp[S], comp[T])}
	match = st & ds
	if len(match) == 0: continue
	[ res.setdefault(decomp[i], []).append(X) for i in match]
[ print(min( res.get(i,[-1] ))) for i in D]

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from operator import itemgetter

N,Q = map(int, input().split())
s = [0]*N
t = [0]*N
x = [0]*N
for i in range(N):
	S,T,X = map(int, input().split())
	s[i] = S-X
	t[i] = T-X
	x[i] = X
D = [ int(input()) for i in range(Q)]
comp = s+t+D
comp = list(set(comp))
comp.sort()

comp = {v:i for i,v in enumerate(comp)}
decomp = {v:k for k,v in comp.items()}
ds = { comp[v] for v in D}
res = {}
for S,T,X in zip(s,t,x):
	st = {i for i in range(comp[S], comp[T])}
	match = st & ds
	for i in match:
		res.setdefault(decomp[i], []).append(X)
[ print(min( res.get(i,[-1] ))) for i in D]

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from bisect import bisect_left,bisect_right
#A.sort(key=itemgetter(1))
N,Q=map(int,input().split())
S=[]
T=[]
S_t=[]
T_t=[]
ans=[]
active_box=[]
for _ in range(N):
    s,t,x=map(int,input().split())
    S.append((s-x,x))
    S_t.append(s-x)
    T.append((t-x,x))
    T_t.append(t-x)
S.sort(key=itemgetter(0))
T.sort(key=itemgetter(0))
S_t.sort()
T_t.sort()
for _ in range(Q):
    d=int(input())
   	#print('ondex{}'.format(_))
    s_i=bisect_right(S_t,d)
    e_i=bisect_right(T_t,d)
    for i in S[0:s_i]:
    	active_box.append(i[1])
    S=S[s_i:]
    S_t=S_t[s_i:]
    #print(T[0:e_i])
    for i in T[0:e_i]:
    	#print(active_box)
    	#print(i)
    	active_box.remove(i[1])
    T=T[e_i:]
    T_t=T_t[e_i:]
    if active_box:
	    print(min(active_box))
    else:
    	print(-1)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
#A.sort(key=itemgetter(1))
N,Q=map(int,input().split())
S=[]
T=[]
ans=[]
active_box=[]
for _ in range(N):
    s,t,x=map(int,input().split())
    S.append((s-x,x))
    T.append((t-x,x))
S.sort(key=itemgetter(0))
T.sort(key=itemgetter(0))
for _ in range(Q):
    d=int(input())
    tmp=S.copy()
   # print('ondex{}'.format(_))
    for i in tmp:
        if i[0]<=d:
        	active_box.append(i[1])
        	S.pop(0)
       # 	print(active_box)
        else:
            break
    tmp=T.copy()
  #  print('aaaaaa')
    for i in tmp:
        if i[0]<=d:
            index=active_box.index(i[1])
          #  print(active_box)
          #  print(index)
            active_box.pop(index)
            T.pop(0)
        else:
            break
    #print(ans)
    if active_box:
	    ans.append(min(active_box))
    else:
    	ans.append(-1)
for i in ans:
  	print(i)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S=[]
T=[]
ans=[]
active_box=[]
for _ in range(N):
    s,t,x=map(int,input().split())
    S.append((s-x,x))
    T.append((t-x,x))
S.sort(key=lambda x:x[0])
T.sort(key=lambda x:x[0])
for _ in range(Q):
    d=int(input())
    tmp=S.copy()
   # print('ondex{}'.format(_))
    for i in tmp:
        if i[0]<=d:
        	active_box.append(i[1])
        	S.pop(0)
       # 	print(active_box)
        else:
            break
    tmp=T.copy()
  #  print('aaaaaa')
    for i in tmp:
        if i[0]<=d:
            index=active_box.index(i[1])
          #  print(active_box)
          #  print(index)
            active_box.pop(index)
            T.pop(0)
        else:
            break
    #print(ans)
    if active_box:
	    ans.append(min(active_box))
    else:
    	ans.append(-1)
for i in ans:
  	print(i)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from operator import itemgetter

N,Q = map(int, input().split())
s = [0]*N
t = [0]*N
x = [0]*N
for i in range(N):
	S,T,X = map(int, input().split())
	s[i] = S-X
	t[i] = T-X
	x[i] = X
d = [ int(input()) for i in range(Q)]
lis = s+t+d
lis = list(set(lis))
lis.sort()

dic = { v:i for i,v in enumerate(lis)}
dic_rev = { v:k for k, v in dic.items()}
res = {}
for S,T,X in zip(s,t,x):
	for i in range(dic[S],dic[T]):
		res.setdefault(dic_rev[i], []).append(X)
#for i in range(Q):
#	ans = res.get(d[i],[-1])
#	print(min(ans))
[ print(min( res.get(i,[-1] ))) for i in d]

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from operator import itemgetter

N,Q = map(int, input().split())
s = [0]*N
t = [0]*N
x = [0]*N
for i in range(N):
	S,T,X = map(int, input().split())
	s[i] = S-X
	t[i] = T-X
	x[i] = X
d = [ int(input()) for i in range(Q)]
lis = s+t+d
lis = list(set(lis))
lis.sort()

dic = { v:i for i,v in enumerate(lis)}
dic_rev = { v:k for k, v in dic.items()}
res = {}
for S,T,X in zip(s,t,x):
	for i in range(dic[S],dic[T]):
		res.setdefault(dic_rev[i], []).append(X)
for i in range(Q):
	ans = res.get(d[i],[-1])
	print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def main():
    kouji_num, person_num = map(int, input().split())
    koji_data = [list(map(int, input().split())) for i in range(kouji_num)]
    person_data = [int(input()) for i in range(person_num)]

    event_list = [0 for i in range(kouji_num * 2)]
    now_kouji = set()

    for i in range(kouji_num):
        start, fin, position = koji_data[i]
        event_list[2 * i] = (start - position - 0.25, 1, position)
        event_list[2 * i + 1] = (fin - position - 0.75, 0, position)
    event_list.sort(key=lambda x: x[0])

    now_ind = 0
    for i in range(person_num):
        person_start = person_data[i]
        while now_ind < kouji_num * 2:
            time_data, flg, position = event_list[now_ind]
            if time_data > person_start:
                break
            if flg:
                now_kouji.add(position)
            else:
                now_kouji.remove(position)
            now_ind += 1
        if len(now_kouji) == 0:
            ans = -1
        else:
            ans = min(now_kouji)
        print(ans)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math

def main():
    kouji_num, person_num = map(int, input().split())
    koji_data = [list(map(int, input().split())) for i in range(kouji_num)]
    person_data = [int(input()) for i in range(person_num)]

    event_list = [0 for i in range(kouji_num * 2)]
    now_kouji = set()

    for i in range(kouji_num):
        start, fin, position = koji_data[i]
        event_list[2 * i] = (start - position - 0.25, 1, position)
        event_list[2 * i + 1] = (fin - position - 0.75, 0, position)
    event_list.sort(key=lambda x: x[0])

    now_ind = 0
    for i in range(person_num):
        person_start = person_data[i]
        while now_ind < kouji_num * 2:
            time_data, flg, position = event_list[now_ind]
            if time_data > person_start:
                break
            if flg:
                now_kouji.add(position)
            else:
                now_kouji.remove(position)
            now_ind += 1
        if len(now_kouji) == 0:
            ans = -1
        else:
            ans = min(now_kouji)
        print(ans)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = defaultdict(lambda: -1)
for x, s, t in roadworks:
    for i in range(s, t+1):
        i = max(0, i-x)
        stops[i] = x
#print(stops)
for d in D:
    print(stops[d+1])