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 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:]))
max_d = ddd[-1]
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    sx = s - x
    tx = t - x
    if tx <= 0 or sx > max_d:
        continue
    ss = bisect_left(ddd, sx)
    tt = bisect_left(ddd, tx)
    if ss == tt:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
rut.propagate()
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))

Submission status: Time Limit Exceeded

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

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

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

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

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

#E
def E():
    def change(t,f,x):
        if f:
            ans.add(x)
        else:
            ans.remove(x)
    n,q = LI()
    l = LIR(n)
    eve = []
    ans = set([float("inf")])
    for i in range(n):
        s,t,x = l[i]
        eve.append((s-x,1,x))
        eve.append((t-x,0,x))
    eve.sort()
    d = IR(q)
    k = 0
    for i in range(q):
        while k < 2*n and eve[k][0] <= d[i]:
            change(eve[k][0],eve[k][1],eve[k][2])
            k += 1
        a = min(ans)
        if a == float("inf"):
            print(-1)
        else:
            print(a)
    return

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

    return

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

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 = [int(line) for line in 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()
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))

Submission status: Time Limit Exceeded

Solution code:
import collections

def main():
    N, Q = [int(x) for x in input().split()]
    updates = []
    for i in range(N):
        S, T, X = [int(x) for x in input().split()]
        updates.append((S-X, 1, X))
        updates.append((T-X, -1, X))
 
    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(updates)
    for _ in range(Q):
        x = int(input())
        while updates and updates[0][0] <= x:
            coord, tp, val = heapq.heappop(updates)
 
            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)
 
        while active and to_delete[active[0]] > 0:
            to_delete[active[0]] -= 1
            heapq.heappop(active)
        print active[0] if active else -1

######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def can_go(status, constructor):
  #print(status, constructor)
  for x in constructor:
    if x[0]-0.5<=status['time'] and status['time']<=x[1]-0.5 and status['pos']==x[2]:
      return True
  return False

cons, people = input().split()

a = 0
constructor = []
while a<int(cons):
  tmp = input().split()
  tmp2 = [int(x) for x in tmp]
  constructor.append(tmp2)
  a += 1
constructor.sort(key=lambda x:x[0])
for i in range(int(people)):
  time = int(input())
  status = {'time':time, 'pos':0}
  b = 0
  flag = True
  while b<=100:
    if can_go(status, constructor):
      #print("STOP")
      print(status['pos'])
      flag=False
      break
    else:
      #print("GO")
      status['time'] += 1
      status['pos'] += 1
      b += 1
  if flag:print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, Q = [int(x) for x in input().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 input().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:
import collections

def main():
    N, Q = [int(x) for x in input().split()]
    updates = []
    for i in range(N):
        S, T, X = [int(x) for x in input().split()]
        updates.append((S-X, 1, X))
        updates.append((T-X, -1, X))
 
    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    heapq.heapify(updates)
    for _ in range(Q):
        x = int(input())
        while updates and updates[0][0] <= x:
            coord, tp, val = heapq.heappop(updates)
 
            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)
 
            while active and to_delete[active[0]] > 0:
                to_delete[active[0]] -= 1
                heapq.heappop(active)
        print active[0] if active else -1

######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
import operator

N, Q = map(int, sys.stdin.readline().rstrip().split(" "))
events = []
for _ in range(N):
    S, T, X = map(int, sys.stdin.readline().rstrip().split(" "))
    events.append((S - X, X))
    events.append((T - X, -X))
events.sort(key=operator.itemgetter(0))


pedestrians = []
for i in range(Q):
    D, = map(int, sys.stdin.readline().rstrip().split(" "))
    pedestrians.append((i, D))
pedestrians.sort(key=operator.itemgetter(1))

current_stops = set()
# current_pedestrian = pedestrians.pop(0)

results = []
for i, current_pedestrian in pedestrians:
    while True:
        if len(events) > 0 and events[0][0] <= current_pedestrian:
            event = events.pop(0)
            # print(event)
            if event[1] >= 0:
                current_stops.add(event[1])
            else:
                current_stops.remove(-event[1])
        else:
            break
    # print(current_stops)
    if len(current_stops) > 0:
        stop = min(current_stops)
        # print(current_stops)
        # print(current_pedestrian, stop[2])
        results.append((i, stop))
    else:
        results.append((i, -1))
for i, result in sorted(results, key=operator.itemgetter(0)):
    print(result)

exit(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

N, Q = map(int, input().split())
SmXTmXX = [0] * N
for i in range(N):
    s, t, x = map(int, input().split())
    SmXTmXX[i] = (s - x, t - x, x)
SmXTmXX.sort(key=lambda x: x[0])
# print(SmXTmXX)
D = np.zeros(Q)
for i in range(Q):
    d = int(input())
    D[i] = d

ans = [-1] * Q
for n in range(N):
    di, dj, x = SmXTmXX[n]
    if dj <= 0:
        continue
    i = np.searchsorted(D, di) if di > 0 else 0
    j = np.searchsorted(D, dj)
#     print(f"{i} to {j} is out")
    for k in range(i, j):
        ans[k] = x if ans[k] == -1 else min(ans[k], x)
        # print(f"marked {k} as {x}")
for v in ans:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, q= map(int, input().split())
nlist = []
for i in range(n):
    s, t, x= map(int, input().split())
    nlist.append({'s':s, 't':t, 'x':x})

sorted_items = sorted(
  nlist,
  key = lambda x: x['x']
)

dlist = []
for i in range(q):
    dlist.append(int(input()))

j = 0
for q in dlist:
    i = 0
    dame = False
    for x in sorted_items:
        i += 1
        time = q + x['x']
        if x['s'] <= time and time < x['t']:
            dame = True
            dlist[j] = x['x']
            break

    if not dame:
        dlist[j] = -1

    j += 1

for i in dlist:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
w=[]
for i in range(n):
    w.append([int(i) for i in input().split()])
w=sorted(w,key=lambda x : x[2])
for i in range(q):
    d=int(input())
    for j in w:
        if j[0]<=d+j[2]<j[1]:
            print(j[2])
            break
    else:
        print(-1)

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 = read_int_array()
    updates = []
    for i in range(N):
        S, T, X = read_int_array()
        updates.append((S-X, 1, X))
        updates.append((T-X, -1, X))

    active = []
    to_delete = collections.defaultdict(int)
    import heapq
    updates.sort(reverse=True)
    for _ in range(Q):
        x = read_int()
        while updates and updates[-1][0] <= x:
            coord, tp, val = updates.pop()

            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)

            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:
# -*- coding: utf-8 -*-
n, q= map(int, input().split())
nlist = []
for i in range(n):
    s, t, x= map(int, input().split())
    nlist.append({'s':s, 't':t, 'x':x})

sorted_items = sorted(
  nlist,
  key = lambda x: (x['x'], x['s'])
)

dlist = []
for i in range(q):
    dlist.append(int(input()))

j = 0
for q in dlist:
    i = 0
    dame = False
    for x in sorted_items:
        i += 1
        time = q + x['x']
        if x['s'] <= time and time < x['t']:
            dame = True
            dlist[j] = x['x']
            break

    if not dame:
        dlist[j] = -1

    j += 1

for i in dlist:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int, input().split())
STX = []
for i in range(N):
    S, T, X = map(int, input().split())
    STX.append([S, T, X])

out = defaultdict(lambda: -1)
for out_num, (S, T, X) in enumerate(STX):
    for i in range(max(S-X, 0), max(T-X, 1)):
        if out[i] != -1:
            if out[i] > X:
                out[i] = X
        else:
            out[i] = X
        
for i in range(Q):
    print(out[int(input())])

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 = read_int_array()
    updates = []
    for i in range(N):
        S, T, X = read_int_array()
        updates.append((S-X, 1, X))
        updates.append((T-X, -1, X))

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

            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)

            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:
import numpy as np
from collections import defaultdict
from functools import reduce

# s = input()
# n = int(input())
# A = list(map(int, input().split()))
N, Q = map(int, input().split())


ls = []

for i in range(N):
    s, t, x = map(int, input().split())
    ls.append((s-x, 0, x))
    ls.append((t-x, 1, x))

ls.sort()


l_idx = 0
counter = defaultdict(int)
mini = -1
xs = set()

for _ in range(Q):
    d = int(input())
    while True:
        if l_idx == len(ls):
            print(-1)
            break
        l = ls[l_idx]
        if d < l[0]:
            if len(xs) == 0:
                print(-1)
            else:
                print(min(xs))
            break
        x = l[2]

        if l[1] == 0:
            counter[x] += 1
            xs.add(x)
        else:
            counter[x] -= 1
            if counter[x] == 0:
                xs.remove(x)
        l_idx += 1

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
SmXTmXX = [0] * N
for i in range(N):
    s, t, x = map(int, input().split())
    SmXTmXX[i] = (s - x, t - x, x)
SmXTmXX.sort(key=lambda x: x[0])
# print(SmXTmXX)
D = [0] * Q
for i in range(Q):
    d = int(input())
    D[i] = d

ans = [-1] * Q
i = 0
for n in range(N):
    di, dj, x = SmXTmXX[n]
    if dj <= 0:
        continue
    i = bisect_left(D, di, i) if di > 0 else 0
    j = bisect_left(D, dj, i)
#     print(f"{i} to {j} is out")
    for k in range(i, j):
        ans[k] = x if ans[k] == -1 else min(ans[k], x)
        # print(f"marked {k} as {x}")
for v in ans:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
sList = [list(map(int, input().split())) for i in range(n)]
dList = [int(input()) for i in range(q)]
sList.sort(key=lambda x: x[2])
infinite = True
for i in dList:
  for start, end, place in sList:
    if (i + place >= start) and (i + place < end):
      print(place)
      infinite = False
      break
  if infinite == True:
    print(-1)
  else:
    infinite = True

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

List_R = []

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):
            List_R.append(List_S[j][2])
            flag= 1
            break
    if flag == 0:
        List_R.append(-1)

for i in range(Q):
    print("{}".format(List_R[i]))

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 = read_int_array()
    coords = {10**10, -10**10}
    updates = []
    for i in range(N):
        S, T, X = read_int_array()
        start, end = S-X, T-X
        coords.add(start)
        coords.add(end)
        updates.append((start, 1, X))
        updates.append((end, -1, X))

    updates.sort()
    active = []
    ui = 0
    to_delete = collections.Counter()
    import heapq
    for _ in range(Q):
        x = read_int()
        while ui < len(updates) and updates[ui][0] <= x:
            coord, tp, val = updates[ui]
            ui += 1

            if tp == -1:
                to_delete[val] += 1
            else:
                heapq.heappush(active, val)
                # print("ADD", val)

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

main()

Submission status: Time Limit Exceeded

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

mem = []

for i in range(N):
    s, t, x = map(int, input().split())
    mem.append((x, s-x, t-x))

mem.sort()

for i in range(Q):
    d = int(input())
    ans = -1
    for j in range(N):
        if mem[j][1] <= d < mem[j][2]:
            ans = mem[j][0]
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

stx = sorted(stx,key=lambda x:x[2])

D = [0 for i in range(Q)]
for i in range(Q):
    D[i] = int(input())

ans = [-1 for i in range(Q)]
for i in range(N):
    s,t,x = stx[i]
    for j in range(Q):
        if ans[j] == -1:
            if s-x <= D[j] < t-x:
                # print("input",D[j])
                ans[j] = x
        else:
            pass
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
import bisect
 
n,q = na()
xx = []
 
for i in range(n):
  s,t,x = na()
  xx.append([x,s-0.5-x,t-0.5-x])
 
xx.sort()
ans = []
 
for i in range(q):
  d = ni()
  a = -1
  for vl in xx:
      if vl[1] < d and d < vl[2]:
          a = vl[0]
          break
  ans.append(a)
 
for i in ans:
  print(i)