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:
def main():
    N, Q = map(int, input().split())
    query = [None] * (2 * N + Q)
    for i in range(N):
        S, T, X = map(int, input().split())
        query[i*2] = (S-X, 1, X)
        query[i*2+1] = (T-X, 0, X)
    for i in range(Q):
        D = int(input())
        query[2*N+i] = (D, 2, 0)
    query.sort()
    mn = float("inf")
    construction = set()
    for t, q, x in query:
        if q == 2:
            if mn == float("inf"):
                print(-1)
            else:
                print(mn)
        elif q == 1:
            construction.add(x)
            if x < mn:
                mn = x
        elif q == 0:
            construction.remove(x)
            if mn == x:
                if len(construction):
                    mn = min(construction)
                else:
                    mn = float("inf")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def propagate(self):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if self.data[i] != self.sentinel:
                self.data[l + self.offset:r + self.offset] = [self.data[i]] * (r - l)
                continue
            i <<= 1
            m = (l + r) // 2
            stack.append((i, l, m))
            stack.append((i + 1, m, r))

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = list(map(int, lines[n:]))
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    if ss == tt:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)

rut.propagate()
# rut.debug_print()
print('\n'.join(map(str, rut.data[rut.offset:rut.offset + q])))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
INF = 10**10
evt = []
for i in range(N):
	s,t,x = map(int,input().split())
	evt.append((s-x,1,x))
	evt.append((t-x,-1,x))
ans = [0 for i in range(Q)]
for i in range(Q):
	evt.append((int(input()), 10, i))
evt.sort()

s = set([INF])
cnt = 0
for e in evt:
	if e[1] == 1:
		s.add(e[2])
	elif e[1] == -1:
		s.remove(e[2])
	elif e[1] == 10:
		ans[e[2]] = min(s)

for a in ans:
	print(a if a != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import bisect

n, q = [int(_) for _ in input().split()]

rs = []
for i in range(n):
    s, t, x = [int(_) for _ in input().split()]
    rs.append((s - x, x))
    rs.append((t - x, ~x))

rs.sort()
dks = [-1] * (2 * n)
dvs = [-1] * (2 * n)
sts = set()
msts = -1
for j, (i, x) in enumerate(rs):
    if x < 0:
        sts.remove(~x)
        msts = msts if msts != ~x else min(sts) if sts else -1
    else:
        sts.add(x)
        msts = x if msts == -1 else min(msts, x)
    dks[j] = i
    dvs[j] = msts


for _ in range(q):
    d = int(input())
    i = bisect.bisect(dks, d) - 1
    if 0 <= i < len(dks) - 1 and dks[i] <= d < dks[i + 1]:
        print(dvs[i])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
n,Q = [int(i) for i in input().split()]
from heapq import  *

stx=[]
for j in range(n):
    a = [int(i) for i in input().split()]
    stx.append([a[1]-a[2],0,a[2]])
    stx.append([a[0]-a[2],1,a[2]])
q = [int(input()) for i in range(Q)]
stx.sort()
s=set()

#print(stx)
pt=0
for i in q:
    while pt < 2*n and i >= stx[pt][0]:
        st,lr,x=stx[pt]
        if lr == 1:
            s.add(x)
        else:
            s.remove(x)
        pt+=1
#    print(s)
    if s:
        print(min(s))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import collections
import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


class Node:

    def __init__(self, start, end):
        self.start, self.end, self.mid = start, end, (start + end) // 2
        self.val = float('inf')
        self.left = self.right = None


class NumArray:

    def __init__(self, x):
        x.sort()
        self.x_i = {v: i for i, v in enumerate(x)}

        def createTree(l, r):
            if l >= r:
                return None
            root = Node(l, r)
            if l + 1 == r:
                return root
            mid = root.mid
            root.left = createTree(l, mid)
            root.right = createTree(mid, r)
            return root

        self.root = createTree(0, len(x) - 1)

    def update(self, x1, x2, val):
        def updateVal(root, i, j):
            if root.start == i and root.end == j:
                root.val = min(root.val, val)
            else:
                mid = root.mid
                if i < mid:
                    updateVal(root.left, i, min(mid, j))
                if mid < j:
                    updateVal(root.right, max(mid, i), j)

        return updateVal(self.root, self.x_i[x1], self.x_i[x2])

    def query(self, x):
        def queryVal(root, i):
            if not root or i < root.start or i >= root.end:
                return float('inf')
            else:
                return min(root.val, queryVal(root.left, i), queryVal(root.right, i))

        return queryVal(self.root, self.x_i[x])


def main():
    N, Q = [int(x) for x in input().split()]
    coords = {10 ** 10, -10 ** 10}
    updates = []
    for i in range(N):
        S, T, X = [int(x) for x in input().split()]
        start, end = S - X, T - X
        coords.add(start)
        coords.add(end)
        coords.add(end)
        updates.append((start, end, X))

    ppl = []
    for i in range(Q):
        x = int(input())
        ppl.append(x)
        coords.add(x)

    st = NumArray(list(coords))
    for s, e, x in updates:
        st.update(s, e, x)
    for x in ppl:
        ans = st.query(x)
        print(ans if ans < float('inf') else -1)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input

N, Q = map(int, input().split())
INF = 10 ** 9
ans = [INF] * Q
stops = [0] * N
times = []
for i in range(N):
    s, t, x = map(int, input().split())
    times.append((s-x, 0, i))
    times.append((t-x, -1, i))
    stops[i] = x
for i in range(Q):
    d = int(input())
    times.append((d, 1, i))

times.sort()
pque = []
used = [False] * N
for t, k, i in times:
    #print(t, k, i)
    if k == -1:
        used[i] = True
    elif k == 0:
        heapq.heappush(pque, (stops[i], i))
    else:
        while pque:
            x, j = heapq.heappop(pque)
            if not used[j]:
                ans[i] = min(ans[i], x)
                heapq.heappush(pque, (x, j))
                break
for x in ans:
    if x != INF:
        print(x)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
INF = 10**10
evt = []
for i in range(N):
	s,t,x = map(int,input().split())
	evt.append((s-x,1,x))
	evt.append((t-x,-1,x))
q = []
ans = [0 for i in range(Q)]
for i in range(Q):
	d = int(input())
	evt.append((d, 10, i))
evt.sort()

s = set([INF])
cnt = 0
for e in evt:
	if e[1] == 1:
		s.add(e[2])
	elif e[1] == -1:
		s.remove(e[2])
	elif e[1] == 10:
		ans[e[2]] = min(s)

for a in ans:
	print(a if a != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT

import heapq
N,Q=list(map(int,raw_input().strip().split(' ')))

Intervals=[]
Ds=[]
start={}
end={}
dic_on=[]
for _ in xrange(N):
    S,T,X=list(map(int,raw_input().strip().split(' ')))
    Intervals+=[(X,S-X-0.5,T-X-0.5)]

for _ in xrange(Q):
    Ds+=[int(input())]

Intervals=sorted(Intervals)
for i in xrange(len(Intervals)):
    X,left,right= Intervals[i]
    if left in start:
        start[left]+=[i]
    else:
        start[left]=[i]

    if right in end:
        end[right]+=[i]
    else:
        end[right]=[i]

all_points=Ds[:]

checked={}
for i in xrange(len(Intervals)):
    X,left,right=Intervals[i]
    if left not in checked:
        all_points+=[left]
        checked[left]=1
    if right not in checked:
        all_points+=[right]
        checked[right]=1


ans=[]
import heapq
online={}
min_online=[]
for i in xrange(len(Intervals)):
    online[i]=0
all_points=sorted(all_points)
s=''
for p in all_points:
    #print(min_online,p)
    if type(p)==type(0.5):
        if p in start:
            for index in start[p]:
                heapq.heappush(min_online,index)
                online[index]=1
        if p in end:
            for index in end[p]:
                online[index]=0

    else:
        x=-1
        while min_online:
            y=heapq.heappop(min_online)
            if online[y]==1:
                x=y
                heapq.heappush(min_online,x)
                break
        ans+=[x]
        if x==-1:
            #print(-1)
            s+="-1\n"
        else:
            #print(Intervals[x][0])
            s+=str(Intervals[x][0])+"\n"

print(s)

Submission status: Time Limit Exceeded

Solution code:
N,Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

L = [(s-x-0.5, t-x-0.5,x) for s,t,x in STX] + [(d,) for d in D]
L.sort()

import heapq
hp = [] # (x,t-x)を入れる

for l in L:
  if len(l)==1:
    while hp and l[0] > hp[0][1]:
      heapq.heappop(hp)
    if hp:
      print(hp[0][0])
    else:
      print(-1)
  else:
    heapq.heappush(hp, (l[2],l[1]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
N, Q = [int(x) for x in stdin.readline().rstrip().split()]
STX = np.zeros((N, 3))
for i in range(N):
    STX[i, 0], STX[i, 1], STX[i, 2] = [int(x) for x in stdin.readline().rstrip().split()]
D = [int(input()) for _ in range(Q)]
STX = STX[np.argsort(STX[:, 2])]

for d in D:
    STX_copy = np.copy(STX)
    STX_copy[:, :2] = STX_copy[:, :2] - d
    try:
        print(int(STX_copy[np.where((STX_copy[:, 0] - 0.5 <= STX_copy[:, 2]) & (STX_copy[:, 1] - 0.5 >= STX_copy[:, 2]))][0, 2]))
    except:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

L = [(max(-0.5,s-x-0.5),max(-0.5,t-x-0.5),x) for s,t,x in STX] + [(d,-1) for d in D]
L.sort()

import heapq
hp = [] # (x,t-x)を入れる

for l in L:
  if l[1] == -1:
    while hp and l[0] > hp[0][1]:
      heapq.heappop(hp)
    if hp:
      print(hp[0][0])
    else:
      print(-1)
  else:
    heapq.heappush(hp, (l[2],l[1]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input

N, Q = map(int, input().split())
INF = 10 ** 9
ans = [INF] * Q
stops = [0] * N
times = []
for i in range(N):
    s, t, x = map(int, input().split())
    times.append((s-x, 0, i))
    times.append((t-x, -1, i))
    stops[i] = x
for i in range(Q):
    d = int(input())
    times.append((d, 1, i))

times.sort()
pque = []
used = set()
for t, k, i in times:
    #print(t, k, i)
    if k == -1:
        used.add(i)
    elif k == 0:
        heapq.heappush(pque, (stops[i], i))
    else:
        while pque:
            x, j = heapq.heappop(pque)
            if j not in used:
                ans[i] = min(ans[i], x)
                heapq.heappush(pque, (x, j))
                break
for x in ans:
    if x != INF:
        print(x)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
List_S = [list(map(int,input().split())) for i in range(N)]
List_D = [int(input()) for i in range(Q)]

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

for i in range(Q):
    flag = 0
    for j in range(N):
        if (List_S[j][0]-0.5 < (List_D[i] + List_S[j][2])) and ((List_D[i] + List_S[j][2]) < List_S[j][1]-0.5):
            print("{}".format(List_S[j][2]))
            flag = 1
            break
    if flag == 0:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def propagate(self):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if self.data[i] != self.sentinel:
                self.data[l + self.offset:r + self.offset] = [self.data[i]] * (r - l)
                continue
            i <<= 1
            m = (l + r) // 2
            stack.append((i, l, m))
            stack.append((i + 1, m, r))

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = list(map(int, lines[n:]))
rut = RangeUpdateTree(q)
i = 0
while i < n:
    x, s, t = kkk[i]

    while i < n - 1 and kkk[i + 1][0] == x and kkk[i + 1][2] == s:
        i += 1
        s = kkk[i][1]

    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    if ss == tt:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
    i += 1

rut.propagate()
# rut.debug_print()
print('\n'.join(map(str, rut.data[rut.offset:rut.offset + q])))

Submission status: Time Limit Exceeded

Solution code:
import heapq

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input

N, Q = map(int, input().split())
INF = 10 ** 10
ans = [INF] * Q
stops = [0] * N
times = []
for i in range(N):
    s, t, x = map(int, input().split())
    times.append((s-x, 0, i))
    times.append((t-x, -1, i))
    stops[i] = x
for i in range(Q):
    d = int(input())
    times.append((d, 1, i))

times.sort()
pque = []
used = set()
for t, k, i in times:
    #print(t, k, i)
    if k == -1:
        used.add(i)
    elif k == 0:
        heapq.heappush(pque, (stops[i], i))
    else:
        while pque:
            if pque[0][1] not in used:
                ans[i] = min(ans[i], pque[0][0])
                break
            heapq.heappop(pque)
        else:
            ans[i] = -1
for x in ans:
    if x != INF:
        print(x)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,Q=list(map(int,input().strip().split(' ')))

Intervals=[]
Ds=[]
start={}
end={}
dic_on=[]
for _ in range(N):
    S,T,X=list(map(int,input().strip().split(' ')))
    Intervals+=[(X,S-X-0.5,T-X-0.5)]

for _ in range(Q):
    Ds+=[int(input())]

Intervals=sorted(Intervals)
for i in range(len(Intervals)):
    X,left,right= Intervals[i]
    if left in start:
        start[left]+=[i]
    else:
        start[left]=[i]

    if right in end:
        end[right]+=[i]
    else:
        end[right]=[i]

all_points=Ds[:]

for I in Intervals:
    X,left,right=I
    all_points+=[left,right]

all_points=sorted(all_points)

ans=[]
import heapq
online={}
min_online=[]
for i in range(len(Intervals)):
    online[i]=0
all_points=sorted(list(set(all_points)))
for p in all_points:
    #print(min_online,p)
    if type(p)==type(0.5):
        if p in start:
            for index in start[p]:
                heapq.heappush(min_online,index)
                online[index]=1
        if p in end:
            for index in end[p]:
                online[index]=0

    else:
        x=-1
        while min_online:
            y=heapq.heappop(min_online)
            if online[y]==1:
                x=y
                heapq.heappush(min_online,x)
                break
        ans+=[x]
        if x==-1:
            print(-1)
        else:
            print(Intervals[x][0])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


N, Q = input().split()

N = int(N)
Q = int(Q)

S = np.zeros([N,3])

for i in range(N):
    S[i,:] = input().split()

D = np.zeros([Q])
for i in range(Q):
    D[i] = input()


S = S[np.argsort(S[:,2])]

for q in range(Q):
    for i in range(N):
            
        d1 = S[i,0] - 0.5 - D[q]
        d2 = S[i,1] - 0.5 - D[q]
            
        if d1 - S[i,2] < 0 and d2 - S[i,2] > 0:
            print(int(S[i,2]))
            break

    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
List_S = [list(map(int,input().split())) for i in range(N)]
List_D = [int(input()) for i in range(Q)]

List_S.sort(key=lambda x:x[2])

for i in range(Q):
    flag = 0
    for j in range(N):
        if (List_S[j][0]-0.5 < (List_D[i] + List_S[j][2])) and ((List_D[i] + List_S[j][2]) < List_S[j][1]-0.5):
            print("{}".format(List_S[j][2]))
            flag = 1
            break
    if flag == 0:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heapify

N, Q = map(int, input().split())
INF = 10 ** 9
ev, pos, D = [], [], []
for _ in range(N):
    s, t, x = map(int, input().split())
    # append event
    ev.append((s-x, 1, x))
    # delete event
    ev.append((t-x, -1, x))

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

ev.sort()

tm = -INF
iev = 0
for d in D:
    # work event
    while iev < N*2:
        nt, ni, nx = ev[iev]
        if nt > d:
            break
        if ni == 1:
            heappush(pos, nx)
            # pos.add(nx)
        else:
            pos.remove(nx)
            heapify(pos)

        tm = nt
        iev += 1
    if len(pos) == 0:
        print(-1)
    else:
        print(pos[0])

Submission status: Time Limit Exceeded

Solution code:
import heapq

import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input

N, Q = map(int, input().split())
INF = 10 ** 10
ans = [INF] * Q
stops = [0] * N
times = []
for i in range(N):
    s, t, x = map(int, input().split())
    times.append((s-x, 0, i))
    times.append((t-x, -1, i))
    stops[i] = x
for i in range(Q):
    d = int(input())
    times.append((d, 1, i))

times.sort()
pque = []
used = set()
for t, k, i in times:
    #print(t, k, i)
    if k == -1:
        used.add(i)
    elif k == 0:
        heapq.heappush(pque, (stops[i], i))
    else:
        while pque:
            x, j = heapq.heappop(pque)
            if j not in used:
                ans[i] = min(ans[i], x)
                heapq.heappush(pque, (x, j))
                break
        else:
            ans[i] = -1
for x in ans:
    if x != INF:
        print(x)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
# stx = [list(map(int, input().split())) for _ in range(n)]
# dep_time = [int(input()) for _ in range(q)]

# max_t = dep_time[-1]+1
# time = {dep_t:-1 for dep_t in dep_time}

# for i in range(n):
# 	s, t, x = stx[i]
# 	for ti in range(max(0,s-x), min(t-x,max_t-1)):
# 		if ti not in time: continue
# 		if time[ti]<0 or time[ti]>x:
# 			time[ti] = x

# for dep_t in dep_time:
# 	print(time[dep_t])


events = []
for _ in range(n):
	s,t,x = map(int, input().split())
	e1 = (max(0,s-x), 1, x)
	e2 = (max(0,t-x), -1, x)
	events.append(e1)
	events.append(e2)

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

dep_time = [int(input()) for _ in range(q)]

working = []
current_t = -1
for event in events:
	if current_t < event[0]:
		for t in range(current_t, event[0]):
			if t in dep_time:
				if working:
					print(min(working))
				else:
					print(-1)
		current_t = event[0]

	if event[1] == 1:
		working.append(event[2])
	elif event[1] == -1:
		working.remove(event[2])

for t in range(current_t, dep_time[-1]+1):
	if t in dep_time:
		if working:
			print(min(working))
		else:
			print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def propagate(self):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if self.data[i] != self.sentinel:
                self.data[l + self.offset:r + self.offset] = [self.data[i]] * (r - l)
                continue
            i <<= 1
            m = (l + r) // 2
            stack.append((i, l, m))
            stack.append((i + 1, m, r))

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = list(map(int, lines[n:]))
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    if ss == tt:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
rut.propagate()
# rut.debug_print()
print('\n'.join(map(str, rut.data[rut.offset:rut.offset + q])))

Submission status: Time Limit Exceeded

Solution code:
import collections


def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    N, Q = [int(x) for x in input().split()]
    updates1 = []
    updates2 = []
    for i in range(N):
        S, T, X = [int(x) for x in input().split()]
        updates1.append((S - X, X))
        updates2.append((T - X, X))

    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(updates1)
    heapq.heapify(updates2)
    for _ in range(Q):
        x = int(input())
        while updates1 and updates1[0][0] <= x:
            coord, val = heapq.heappop(updates1)
            heapq.heappush(active, val)

        while updates2 and updates2[0][0] <= x:
            coord, val = heapq.heappop(updates2)
            to_delete[val] += 1

        while active and to_delete[active[0]] > 0:
            to_delete[active[0]] -= 1
            heapq.heappop(active)
        write(active[0] if active else -1)

main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
INF = 10 ** 9
ev, pos, D = [], set(), []
for _ in range(N):
    s, t, x = map(int, input().split())
    # append event
    ev.append((s-x, 1, x))
    # delete event
    ev.append((t-x, -1, x))

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

ev.sort()

def stop(x, s, t, d):
    arv = d + x
    if s <= arv < t:
        return 1
    elif arv >= t:
        return 2
    return 0

tm = -INF
iev = 0
for d in D:
    # work event
    while iev < N*2:
        nt, ni, nx = ev[iev]
        if nt > d:
            break
        if ni == 1:
            pos.add(nx)
        else:
            pos.remove(nx)
        tm = nt
        iev += 1
    if len(pos) == 0:
        print(-1)
    else:
        print(min(pos))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
STX_s = [list(map(int,input().split())) for _ in range(N)] 
D = [int(input()) for _ in range(Q)]

STX_s = sorted(STX_s, key= lambda x:x[2])
for d in D:
  for STX in STX_s:
    S = STX[0]
    T = STX[1]
    X = STX[2]
    if S-X <= d < T-X:
      print(X)
      break
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIT = lambda: tuple(MI())
MIS = lambda: input().split()


def main():
    N, Q = MI()
    WS = tuple((MIT() for _ in range(N)))
    D = tuple((II() for _ in range(Q)))
    Tevent = []

    for S, T, X in WS:
        Tevent.append((S-X, True, X))
        Tevent.append((T-X, False, X))
    Tevent.sort()

    ts = set()
    ti = 0
    for d in D:
        while ti < len(Tevent) and Tevent[ti][0] <= d:
            t, event, x = Tevent[ti]
            if event:
                ts.add(x)
            else:
                ts.remove(x)
            ti += 1

        print(min(ts) if ts else -1)


if __name__ == "__main__":
    main()