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/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin



def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [0]*Q + [10**10]
  ans = {}
  for i in range(Q):
    Dn[i] = int(stdin.readline().rstrip())
    ans[Dn[i]] = -1

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from sys import stdin



def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [0]*Q + [10**10]
  ans = {}
  for i in range(Q):
    Dn[i] = int(stdin.readline().rstrip())
    ans[Dn[i]] = -1

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
from sys import stdin



def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [0]*Q + [10**10]
  ans = {}
  for i in range(Q):
    Dn[i] = int(stdin.readline().rstrip())
    ans[Dn[i]] = -1

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque


def main():
  ## input
  N,Q = map(int, input().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, input().split())
    STX[i] = [x,s-x,t-x]
  Dn = [10**10] * (Q+1)
  ans = {}
  for i in range(Q):
    Dn[i] = int(input())
    ans[Dn[i]] = -1

  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
from sys import stdin,stdout


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [10**10] * (Q+1)
  ans = {}
  for i in range(Q):
    Dn[i] = int(stdin.readline().rstrip())
    ans[Dn[i]] = -1

  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
from sys import stdin,stdout


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)]+[10**10]

  ans = {}
  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)
  for d in Dn[:-1]:
    ans[d] = -1

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque,defaultdict


def main():
  ## input
  N,Q = map(int, input().split())
  STX = deque()
  for i in range(N):
    s,t,x = map(int, input().split())
    STX.append([x,s-x,t-x])
  Dn = [int(input()) for _ in range(Q)]+[10**10]

  ans = {}
  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)
  for d in Dn[:-1]:
    ans[d] = -1

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque,defaultdict
from sys import stdin,stdout


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = deque()
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX.append([x,s-x,t-x])
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)]+[10**10]

  ans = defaultdict(lambda:-1)
  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)
  for d in Dn[:-1]:
    ans[d] = -1

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
from sys import stdin,stdout


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = deque()
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX.append([x,s-x,t-x])
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)]+[10**10]

  ans = []
  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      heappush(ans,(Dn[l],x))
      Dn.pop(l)
  for d in Dn:
    heappush(ans,(d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans)>1:
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
import sys


def main():
  ## input
  N,Q = map(int, sys.stdin.readline().rstrip().split())
  STX = []
  for i in range(N):
    s,t,x = map(int, sys.stdin.readline().rstrip().split())
    heappush(STX, (x, s-x, t-x))
  Dn = [int(sys.stdin.readline().rstrip()) for _ in range(Q)]+[10**10]

  ans = []
  while len(STX) > 0:
    x,s,t = heappop(STX)
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      heappush(ans,(Dn[l],x))
      Dn.pop(l)
  for d in Dn:
    heappush(ans,(d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans)>1:
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque


def main():
  ## input
  N,Q = map(int, input().split())
  STX = [[0,0,0] for i in range(N)]
  for i in range(N):
    s,t,x = map(int, input().split())
    STX[i] = [s-x, t-x-1, x]
  STX = sorted(STX, key=lambda x:x[2])
  Dn = [int(input()) for _ in range(Q)]+[10**10]

  ans = []
  for s,t,x in STX:
    l = bisect_left(Dn,s)
    while Dn[l] <= t:
      heappush(ans,(Dn[l],x))
      Dn.pop(l)
  for d in Dn:
    heappush(ans,(d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans)>1:
    print(heappop(ans)[1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
import bisect
import heapq
from collections import deque


def main():
  ## input
  N,Q = map(int, input().split())
  STX = [[0,0,0] for i in range(N)]
  for i in range(N):
    s,t,x = map(int, input().split())
    STX[i] = [s-x, t-x-1, x]
  STX = sorted(STX, key=lambda x:x[2])
  Dn = [int(input()) for _ in range(Q)]+[10**10]

  ans = []
  for s,t,x in STX:
    l = bisect.bisect_left(Dn,s)
    r = bisect.bisect_right(Dn,t)-1
    while Dn[l] <= t:
      heapq.heappush(ans,(Dn[l],x))
      Dn.pop(l)
  for d in Dn:
    heapq.heappush(ans,(d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans)>1:
    print(heapq.heappop(ans)[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)]

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

L = [-1] * Q
T = [-1] * Q
for s, t, x in STX:
  n = s - x
  ok = Q
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  l = ok

  n = t - x
  ok = Q
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  r = ok

  while l < r:
    if T[l] == -1:
      T[l], L[l] = r, x
      l += 1
    else:
      l = T[l]

for i in L:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
import bisect
from collections import deque



def main():
  ## input
  N,Q = map(int, input().split())
  STX = [[0,0,0] for i in range(N)]
  for i in range(N):
    s,t,x = map(int, input().split())
    STX[i] = [s-x, t-x-1, x]
  STX = sorted(STX, key=lambda x:x[2])
  Dn = [int(input()) for _ in range(Q)]+[10**10]

  ans = deque()
  for s,t,x in STX:
    l = bisect.bisect_left(Dn,s)
    r = bisect.bisect_right(Dn,t)-1
    for i in range(r,l-1,-1):
      if Dn[i]>=s and Dn[i]<=t:
        ans.append([Dn[i],x])
        Dn.pop(i)
  for d in Dn:
    ans.append([d,-1])
  
  ret = [x[1] for x in sorted(list(ans))[:-1]]
  return ret


if __name__ == "__main__":
  ans = main()
  [print(a) for a in ans]

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_right

input = sys.stdin.readline

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

e = []
for _ in range(N):
    S, T, X = map(int, input().split())
    e.append([X, S - X, T - X])
e.sort()

s = []
for i in range(Q):
    D = int(input())
    s.append((D, i))
s.sort()

ans = [-1] * Q
for i in range(N):
    x, l, r = e[i]
    j = bisect_right(s, (l, -1))
    while j < len(s):
        if s[j][0] >= r:
            break
        ans[s[j][1]] = x
        s.pop(j)
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
def newXvalues(Xvalues,t,operation,x):
    """
    Xvalues: list, t = Si-Xi or Ti-Xi, operation = 1 or -1
    x = Xi
    """
    if operation == 1:  # insert
        Xvalues.append(x)
    else:
        Xvalues.remove(x)  # delete
    return Xvalues

N, Q = map(int,input().split(' '))
event = []
n = 0
while n < N:
    s,t,x = map(int,input().split(' '))
    event.append((s-x,1,x))
    event.append((t-x,-1,x))
    n += 1
event.sort()
Dlist = []
q = 0
while q < Q:
    d0 = int(input())
    Dlist.append((d0,q))
    q += 1
Dlist.sort()
ans = [-1]*Q
Xvalues = []
e = 0
for D0 in Dlist:
    while e < len(event) and event[e][0] <= D0[0]:
        Xvalues = newXvalues(Xvalues, event[e][0],event[e][1],event[e][2])
        e += 1
    if len(Xvalues) != 0:
        ans[D0[1]] = min(Xvalues)
answer = ""
for a in ans:
    answer += str(a) + '\n'
print(answer[:-1])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = []
for iR in range(N):
    S, T, X = map(int, input().split())
    events.append((S-X, 0, X, iR))
    events.append((T-X, 1, -X, iR))
events.sort()

iE = 0
isActives = [False] * N
anss = []
PQ = []
for _ in range(Q):
    D = int(input())
    while iE < 2*N and events[iE][0] <= D:
        tm, ST, x, iR = events[iE]
        if ST == 0:
            isActives[iR] = True
            heappush(PQ, (x, iR))
        else:
            isActives[iR] = False
        iE += 1

    xMin = -1
    while PQ:
        x, iR = heappop(PQ)
        if isActives[iR]:
            xMin = x
            heappush(PQ, (x, iR))
            break
    anss.append(xMin)

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
roadworks = [tuple(map(int, input().split())) for _ in range(N)]
Ds = [int(input()) for _ in range(Q)]

events = []
for iR, (S, T, X) in enumerate(roadworks):
    events.append((S-X, 0, X, iR))
    events.append((T-X, 1, -X, iR))
events.sort()

iE = 0
isActives = [False] * N
anss = []
PQ = []
for D in Ds:
    while iE < 2*N and events[iE][0] <= D:
        tm, ST, x, iR = events[iE]
        if ST == 0:
            isActives[iR] = True
            heappush(PQ, (x, iR))
        else:
            isActives[iR] = False
        iE += 1

    xMin = -1
    while PQ:
        x, iR = heappop(PQ)
        if isActives[iR]:
            xMin = x
            heappush(PQ, (x, iR))
            break
    anss.append(xMin)

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

Submission status: Time Limit Exceeded

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

D = [0]*Q
Input = []
length = [-1]*Q

for i in range(N):
    Input.append(list(map(int,input().split())))

dist = lambda A : A[2]
Input.sort(key=dist)

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

# i番目の人の座標を計算
for i in range(Q):
    for j in range(N):
        if(Input[j][1] <= D[i]): # 工事終了時刻 <= 出発時刻
            continue

        stopTime = Input[j][2] + D[i] # 出発時刻 + 距離/速度

        if(stopTime >= Input[j][0] - 0.5 and stopTime <= Input[j][1] - 0.5):
            length[i] = Input[j][2]
            break

for l in length:
    print(l)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x,-x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if w>=0:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[-w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x-0.5,x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if int(p[cnt][0]) == p[cnt][0]:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(tank)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x-0.5,x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if int(p[cnt][0]) == p[cnt][0]:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = heapq.heappop(tank)
            if used[kouho] > 0:
                print(kouho)
                heapq.heappush(tank,kouho)
                break
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys,heapq
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = {}
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x-0.5,x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if int(p[cnt][0]) == p[cnt][0]:
                if w in used:
                    used[w] += 1
                else:
                    used[w] = 1
                heapq.heappush(tank,w)
            else:
                used[w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = heapq.heappop(tank)
            if used[kouho] > 0:
                print(kouho)
                heapq.heappush(tank,kouho)
                break
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

events = []
for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))

events.sort()

koujichu = set()

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.add(events[i][2])
        else:
            koujichu.remove(events[i][2])
        i += 1
    if len(koujichu):
        print(min(koujichu))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')
N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = np.array([int(next(sys.stdin)) for _ in range(Q)])

ans = np.full(Q, np.inf)

for s, t, x in STX:
    # [lo, hi) に出発した人は x で止まる
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    ans[lo:hi] = np.minimum(x, ans[lo:hi])

for a in ans:
    print(int(a) if a < np.inf else -1)

Submission status: Time Limit Exceeded

Solution code:
# from heapq import heappush, heapify
# from bisect import insort_left

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


for _ in range(Q):
    # insort_left(event, (int(input()), 3, 0))
    event.append((int(input()), 3, 0))

event.sort()

min_valid, min_val = True, INF
for ev in event:
    # work event
    time, type, x = ev
    if type == 2:
        if min_valid:
            min_val = min(min_val, x)
        pos[x] = True
        # pos.append(x)
        # heappush(pos, x)
    elif type == 1:
        del pos[x]
        min_valid = False
        # pos.remove(x)
        # heapify(pos)
    else:
        if len(pos) == 0:
            print(-1)
        else:
            if not min_valid:
                min_val = min(pos.keys())
                min_valid = True
            print(min_val)
            # print(pos[0])

Submission status: Time Limit Exceeded

Solution code:
# from heapq import heappush, heapify
from bisect import insort_left

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

event.sort()

for _ in range(Q):
    insort_left(event, (int(input()), 3, 0))
    # event.append((int(input()), 3, 0))

for ev in event:
    # work event
    time, type, x = ev
    if type == 2:
        pos[x] = True
        # pos.append(x)
        # heappush(pos, x)
    elif type == 1:
        del pos[x]
        # pos.remove(x)
        # heapify(pos)
    else:
        if len(pos) == 0:
            print(-1)
        else:
            print(min(pos.keys()))
            # print(pos[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')
MAXINT = sys.maxsize

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

ans = np.full(Q, np.inf)

for s, t, x in sorted(STX, key=lambda stx: -stx[2]):
    # [lo, hi) に出発した人は x で止まる
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    ans[lo:hi] = x

for a in ans:
    print(int(a) if a < np.inf else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heapify

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

for _ in range(Q):
    event.append((int(input()), 3, 0))

event.sort()

for ev in event:
    # work event
    time, type, x = ev
    if type == 2:
        pos[x] = True
        # pos.append(x)
        # heappush(pos, x)
    elif type == 1:
        del pos[x]
        # pos.remove(x)
        # heapify(pos)
    else:
        if len(pos) == 0:
            print(-1)
        else:
            print(min(pos.keys()))
            # print(pos[0])

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

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

L = [[-1, -1]] * Q
for s, t, x in STX:
  n = s - x
  ok = Q
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  l = ok

  n = t - x
  ok = Q
  ng = l - 1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  r = ok

  while l < r:
    if L[l][1] == -1:
      L[l] = [x, r]
      l += 1
    else:
      l = L[l][1]

for i in L:
  print(i[0])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

A = []

for i in range(N) :
    S,T,X = map(int,input().split())
    A.append([S-X,1,X])
    A.append([T-X,0,X])

A = sorted(A, key=lambda x: x[0])

B = []

ans = []

for i in range(Q) :
    D = int(input())
    
    while True :
        if not A :
            break
        if A[0][0] > D :
            break
        
        if A[0][1] :
            B.append(A[0][2])
            A.pop(0)
        else :
            B.remove(A[0][2])
            A.pop(0)
    
    if not B :
        res = -1
    else :
        res = min(B)
    
    ans.append(res)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

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

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    n = s - x
    ok = Q
    ng = -1
    while abs(ok - ng) > 1:
      mid = abs(ok + ng) // 2
      if D[mid] >= n:
        ok = mid
      else:
        ng = mid
    l = ok

    n = t - x
    ok = Q
    ng = l - 1
    while abs(ok - ng) > 1:
      mid = abs(ok + ng) // 2
      if D[mid] >= n:
        ok = mid
      else:
        ng = mid
    r = ok

    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Submission status: Time Limit Exceeded

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

A = []

for i in range(N) :
    S,T,X = map(int,input().split())
    A.append([S-X,1,X])
    A.append([T-X,0,X])

A = sorted(A, key=lambda x: x[0])

B = []

ans = []

for i in range(Q) :
    D = int(input())
    
    while True :
        if not A :
            break
        if A[0][0] > D :
            break
        
        if A[0][1] :
            B.append(A[0][2])
            A.pop(0)
        else :
            B.remove(A[0][2])
            A.pop(0)
    
    if not B :
        res = -1
    else :
        res = min(B)
    
    ans.append(res)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
def hersCode(L, n, l):
  ok = len(L)
  ng = l
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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

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

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x, -1)
    r = hersCode(D, t - x, l - 1)

    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Submission status: Time Limit Exceeded

Solution code:
def hersCode(L, n):
  ok = len(L)
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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

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

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)

    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
events = []
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    events.append((s - x, 2, x))
    events.append((t - x, 1, x))
for line in lines[n:]:
    events.append((int(line), 3))
events.sort()

constructing = set()
buf = []
for ev in events:
    if ev[1] == 2:
        constructing.add(ev[2])
    elif ev[1] == 1:
        constructing.remove(ev[2])
    else:
        buf.append(min(constructing) if constructing else -1)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

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

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

ans = []

for d in D :
    d *= -1
    
    for i in range(N) :
        S,T,X = L[i]
        if (X-(T-0.5) <= d) and (d <= X-(S-0.5)) :
            res = X
            #print("wow")
            break
    else :
        res = -1
    
    ans.append(res)

print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:

import bisect
import sys

N, Q = map(int, input().split())
kouzi = []
for _ in range(N):
    S, T, X = map(int, input().split())
    kouzi.append([X, S, T-1])
kouzi.sort(reverse = True)

human = [int(input()) for _ in range(Q)]
ans = [-1]*(Q+1)


N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]
t = 0
for task in kouzi:
    t += 1
    x = task[0]
    l = bisect.bisect_left(human, task[1]-x)
    r = bisect.bisect_right(human, task[2]-x)
    if l == r:
        continue
    update(l, r, (t, x))

for i in range(Q):
    q = query(i)
    if q == 2147483647:
        print(-1)
    else:
        print(q)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
x_dict = {}
max_x = 0
for e in s[1:N + 1]:
    S, T, X = map(int, e.split())
    if X in x_dict:
        for i in range(S - 1, T):
            x_dict[X].add(i + 0.5)
    else:
        x_dict[X] = {S - 0.5}
        for i in range(S, T):
            x_dict[X].add(i + 0.5)
    if max_x < X:
        max_x = X
for e in s[N + 1:]:
    D = int(e)
    inf_flg = 1
    for x_place, x_time_set in sorted(x_dict.items()):
        time = D + x_place + 0.5
        if time in x_time_set:
            print(x_place)
            inf_flg = 0
            break
    if inf_flg == 1:
        print(-1)