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:
#!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():
    n,Q = LI()
    e = []
    for i in range(n):
        s,t,x = LI()
        e.append((s-x,x,1))
        e.append((t-x,x,0))
    e.sort()
    m = 2*n
    q = set()
    j = 0
    ans = float("inf")
    for i in range(Q):
        d = I()
        while j < m:
            t,x,k = e[j]
            if d < t:
                break
            if k:
                q.add(x)
                if x < ans:
                    ans = x
            else:
                q.remove(x)
                if ans == x:
                    if q:
                        ans = min(q)
                    else:
                        ans = float("inf")
            j += 1
        if q:
            print(ans)
        else:
            print(-1)
    return

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

    return

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

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():
    n,Q = LI()
    e = []
    for i in range(n):
        s,t,x = LI()
        e.append((s-x,x,1))
        e.append((t-x,x,0))
    e.sort()
    m = 2*n
    q = set([float("inf")])
    j = 0
    for i in range(Q):
        d = I()
        while j < m:
            t,x,k = e[j]
            if d < t:
                break
            if k:
                q.add(x)
            else:
                q.remove(x)
            j += 1
        mi = min(q)
        print(mi if mi != float("inf") else -1)
    return

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

    return

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

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():
    n,Q = LI()
    e = []
    for i in range(n):
        s,t,x = LI()
        e.append((s-x,x,1,i))
        e.append((t-x,x,0,i))
    e.sort()
    m = 2*n
    f = [0]*(n+1)
    f[n] = 1
    q = [(float("inf"),n)]
    j = 0
    for i in range(Q):
        d = I()
        while j < m:
            t,x,k,l = e[j]
            if d < t:
                break
            if k:
                heappush(q,(x,l))
                f[l] = 1
            else:
                f[l] = 0
                y,k = heappop(q)
                while not f[k]:
                    y,k = heappop(q)
                heappush(q,(y,k))
            j += 1
        y,k = heappop(q)
        heappush(q,(y,k))
        print(y if y != float("inf") else -1)
    return

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

    return

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input=sys.stdin.readline

N,Q=map(int,input().split())
H=[]
for i in range(N):
    s,t,x=map(int,input().split())
    H.append([s-x,t-x,x])
H.sort()
#print(H)
P=0
q=[]
heapq.heapify(q)
for i in range(Q):
    n=int(input())
    #print("A",len(q))
    if P<N:
        while H[P][0]<=n:
            heapq.heappush(q,[H[P][2],H[P][0],H[P][1]])
            P+=1
            if P==N:
                break
    #print("B",i,len(q))
    if len(q)>0:
        while q[0][2]<=n:
            heapq.heappop(q)
            if len(q)==0:
                break
    if len(q)==0:
        print(-1)
    else:
        print(q[0][0])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key = lambda x: x[2])
X.append([-1, 1, X[-1][2] + 1])

def quitConst(t):
  nextx = [x for x in X if x[1] > t + x[2] or x[0] == -1]
  return nextx
def startConst(t):
  nextx = [x for x in X if x[0] <= t + x[2] or x[0] == -1]
  return nextx
for _ in range(Q):
  current = 0
  start = int(input())
  X = quitConst(start)
  XX = startConst(start)
  for x in XX:
    current = x[2]
    if x[0] <= current + start < x[1]:
      break
  if current == XX[-1][2]:
    print(-1)
  else:
    print(current)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key = lambda x: x[2])
X.append([-1, 1, X[-1][2] + 1])

def quitConst(t):
  nextx = [x for x in X if x[1] > t + x[2] or x[0] == -1]
  return nextx

for _ in range(Q):
  current = 0
  start = int(input())
  X = quitConst(start)
  for x in X:
    current = x[2]
    if x[0] <= current + start < x[1]:
      break
  if current == X[-1][2]:
    print(-1)
  else:
    print(current)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort(key = lambda x: x[2])
X.append([-1, 1, X[-1][2] + 1])

def quitConst(t):
  nextx = [x for x in X if x[1] > t or x[0] == -1]
  return nextx

for _ in range(Q):
  current = 0
  start = int(input())
  X = quitConst(start)
  for x in X:
    current = x[2]
    if x[0] <= current + start < x[1]:
      break
  if current == X[-1][2]:
    print(-1)
  else:
    print(current)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
 
 
N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    STX.append(list(map(int, input().split())))
STX.sort(key=lambda x: x[2])
 
kensaku = dict()
for i in range(Q):
    D.append(int(input()))
    kensaku[D[-1]] = i
 
dist = [10000000000000 for i in range(Q)]
 
for i in range(N):
    s = STX[i][0] - STX[i][2]
    t = STX[i][1] - STX[i][2] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    for j in range(a, b):
        dist[kensaku[D[j]]] = min(dist[kensaku[D[j]]], STX[i][2])
    del D[a:b]
 
 
for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
 
 
N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    STX.append(list(map(int, input().split())))
for i in range(Q):
    D.append(int(input()))
 
dist = [10000000000000 for i in range(Q)]
 
for i in range(N):
    s = STX[i][0] - STX[i][2]
    t = STX[i][1] - STX[i][2] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    for j in range(a, b):
        dist[j] = min(dist[j], STX[i][2])
 
 
for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
 
N, Q = map(int, input().split())
 
STX = [list(map(int, input().split())) for _ in range(N)]
# xの昇順に工事の区間をsort
STX = sorted(STX, key=lambda x: x[2])
 
D = [int(input()) for _ in range(Q)]
ans = [-1] * Q
index = [-1] * Q
for s, t, x in STX:
    left = bisect.bisect_left(D, s - x - 0.5)
    right = bisect.bisect_left(D, t - x - 0.5)
    now = left
    while now < right:
        if index[now] == -1:  # まだansが更新されていない場合
            ans[now] = x
            index[now] = right
            now += 1
        else:
            now = index[now]
            
 
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

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

skip = [-1]*Q

dist = [-1]*Q

for (X, S, T) in STX:
    s = S - X
    t = T - X
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_left(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

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

skip = [-1]*Q

dist = [-1]*Q

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

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

skip = [-1]*Q

dist = [10000000000000]*Q

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]



for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

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

skip = [-1 for i in range(Q)]

dist = [10000000000000 for i in range(Q)]

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]



for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    bisect.insort(STX, (X, S, T))
for i in range(Q):
    D.append(int(input()))

skip = [-1 for i in range(Q)]

dist = [10000000000000 for i in range(Q)]

for (X, S, T) in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]



for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    bisect.insort(STX, (X, S, T))

kensaku = dict()
for i in range(Q):
    D.append(int(input()))
    kensaku[D[-1]] = i

dist = [10000000000000 for i in range(Q)]

for i in range(N):
    s = STX[i][1] - STX[i][0]
    t = STX[i][2] - STX[i][0] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    for j in range(a, b):
        dist[kensaku[D[j]]] = min(dist[kensaku[D[j]]], STX[i][0])
    del D[a:b]


for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    STX.append(list(map(int, input().split())))
STX.sort(key=lambda x: x[2])

kensaku = dict()
for i in range(Q):
    D.append(int(input()))
    kensaku[D[-1]] = i

dist = [10000000000000 for i in range(Q)]

for i in range(N):
    s = STX[i][0] - STX[i][2]
    t = STX[i][1] - STX[i][2] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    for j in range(a, b):
        dist[kensaku[D[j]]] = min(dist[kensaku[D[j]]], STX[i][2])
    del D[a:b]


for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


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

dist = [10000000000000 for i in range(Q)]

for i in range(N):
    s = STX[i][0] - STX[i][2]
    t = STX[i][1] - STX[i][2] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    for j in range(a, b):
        dist[j] = min(dist[j], STX[i][2])


for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# random_denseがTLE, 他はAC
from bisect import bisect_left, bisect_right  # 二分探索
def main_tle():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み

    events = []
    for i, d in enumerate(D):
        events.append(('D', d, i))
    for s, t, x in STX:
        events.append(('S', s-x-0.25, x))
        events.append(('T', t-x-0.75, x))  # 0.5 同士だと [1, 2), [0, 1) で吹き飛ぶ
    
    ans = [-1] * Q
    events.sort(key=lambda v: v[1])
    xset = set()
    #xmin = None
    xmin = 1e+10
    xb = False
    for event, time, xi in events:
        if event == 'S':
            xset.add(xi)
            #if xmin is None or xmin > xi:
            if xmin > xi:
                xmin = xi
                xb = True
        elif event == 'T':
            xset.remove(xi)
            if xmin == xi:
                #xmin = None
                xb = False
        elif event == 'D' and xset:
            #if xmin is None:
            if not xb:
                xmin = min(xset)
            ans[xi] = xmin

    for n in ans:
        print(n)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# random_denseがTLE, 他はAC
from bisect import bisect_left, bisect_right  # 二分探索
def main_tle():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み

    events = []
    for i, d in enumerate(D):
        events.append(('D', d, i))
    for s, t, x in STX:
        events.append(('S', (s-x-0.4), x))
        events.append(('T', (t-x-0.6), x))  # 0.5 同士だと [1, 2), [0, 1) で吹き飛ぶ
    
    ans = [-1] * Q
    events.sort(key=lambda v: v[1])
    xset = set()
    xmin = None
    for event, time, xi in events:
        if event == 'S':
            xset.add(xi)
            if xmin is None or xmin > xi:
                xmin = xi
        elif event == 'T':
            xset.remove(xi)
            if xmin == xi:
                xmin = None
        elif event == 'D' and xset:
            if xmin is None:
                xmin = min(xset)
            ans[xi] = min(xset)

    for n in ans:
        print(n)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, Q = i2nn()
    STX = ii2nnn(N) # 座標 X で時刻 [S, T) が工事
    D = ii2nn(Q)    # 昇順ソート済み
    E = [-1] * Q
    STX.sort(key=lambda v: v[2])
    for s, t, x in STX:
        a = bisect_left(D, s-x)
        b = bisect_left(D, t-x)
        for i in range(a, b):
            if E[i] == -1:
                E[i] = x
    for e in E:
        print(e)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
event=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	event.append(  ( s-x ,1, x) )	#Start
	event.append(  ( t-x,-1, x) )	#End


for i in range(Q):
	d=int(sys.stdin.readline().strip())
	event.append(  (d ,0, i) )

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

stop=set()

ans=defaultdict(lambda: -1)
is_stop=False
minstop=float("inf")


for s,flag,x in event:
	if flag==1:
		stop.add(x)
		if x<minstop:
			minstop=x
			is_stop=True
	elif flag==-1:
		try:
			stop.remove(x)
		except:
			pass
		if minstop==x:
			is_stop=False
	elif flag==0:
		if stop:
			if not is_stop:
				minstop=min(stop)
				is_stop=True
			ans[x]=minstop
		else:
			ans[x]=-1


for i in range(Q):
	print (ans[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
event=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	event.append(  ( s-x ,1, x) )	#Start
	event.append(  ( t-x,-1, x) )	#End


for i in range(Q):
	d=int(sys.stdin.readline().strip())
	event.append(  (d ,0, i) )

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

stop=set()

ans=defaultdict(lambda: -1)
is_stop=False
minstop=float("inf")


for s,flag,x in event:
	if flag==1:
		stop.add(x)
		if x<minstop:
			minstop=x
			is_stop=True
	elif flag==-1:
		try:
			stop.remove(x)
		except:
			pass
		if minstop==x:
			is_stop=False
	elif flag==0:
		if stop:
			if not is_stop:
				minstop=min(stop)
				is_stop=True
			ans[x]=minstop
		else:
			ans[x]=-1


for i in range(Q):
	print ans[i]

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify
from collections import defaultdict
import copy
 
N,Q=map(int, sys.stdin.readline().split())
 
S=[]
event=[]
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	event.append(  ( s-x ,1, x) )	#Start
	event.append(  ( t-x,-1, x) )	#End


for i in range(Q):
	d=int(sys.stdin.readline().strip())
	event.append(  (d ,0, i) )

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

stop=set()

ans=defaultdict(lambda: -1) 

for s,flag,x in event:
	if flag==1:
		stop.add(x)
	elif flag==-1:
		try:
			stop.remove(x)
		except:
			pass
	elif flag==0:
		if stop:
			ans[x]=min(stop)
		else:
			ans[x]=-1


for i in range(Q):
	print ans[i]

Submission status: Time Limit Exceeded

Solution code:
def main():

    import sys
    input = sys.stdin.readline
    from bisect import bisect_left

    N,Q = map(int,input().split())
    info = []
    for _ in range(N):
        s,t,x = map(int,input().split())
        info.append((x,s,t))
    info = sorted(info)
    tmp = sorted([(int(input()),i) for i in range(Q)])
    D = []
    ID = []
    for d,i in tmp:
        D.append(d)
        ID.append(i)

    bit = [1]*Q
    ans = [-1]*Q
    for x,s,t in info:
        left = bisect_left(D,s-x)
        right = bisect_left(D,t-x)
        for j in range(left,right):
            i = ID[j]
            if bit[i]:
                ans[i] = x
                bit[i] = 0
    
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop, heapify

N,Q=map(int, sys.stdin.readline().split())

RW=[]	#  Roadwork: 道路工事を行っている場所　(開始時間、終了時間、x座標)
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	RW.append( (max(0,s-x) , max(0,t-1-x),x) )

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

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]	# Q人の歩き出す時刻
D.sort()


d=0
for d in D:
	hq=[]
	for s,t,x in RW:
		if s<=d<=t:
			heappush(hq, x)

		if hq:
			print hq[0]
			break
	else:
		print -1

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush, heappop

N,Q=map(int, sys.stdin.readline().split())

RW=[]	#  Roadwork: 道路工事を行っている場所　(開始時間、終了時間、x座標)
for _ in range(N):
	s,t,x=map(int, sys.stdin.readline().split())
	RW.append( (max(0,s-x) , max(0,t-1-x),x) )

RW.sort(key=lambda x:(x[0],x[1]) )

D=[ int(sys.stdin.readline().strip()) for _ in range(Q) ]	# Q人の歩き出す時刻
D.sort()


d=0
for d in D:
	hq=[]
	for s,t,x in RW:
		if s<=d<=t:
			heappush(hq, x)
		elif d<s:
			break

	try:
		print hq[0]
	except:
		print -1