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: Wrong Answer

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())
	heappush( RW,(max(0,s-x) , max(0,t-1-x),x) )

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 t<d:
			heappop(RW)

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

Submission status: Wrong Answer

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

heapify(RW)

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 t<d:
			heappop(RW)

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [(int(input()), i) for i in range(Q)]
    D.sort(key=itemgetter(0))
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, (S-X, 0))
        r = bisect_right(D, (T-X, 0))
        for i in range(l, r):
            idx = D[i][1]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [(int(input()), i) for i in range(Q)]
    constructions.sort(key=itemgetter(2))
    D.sort()
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, (S-X, 0))
        r = bisect_right(D, (T-X, 0))
        for i in range(l, r):
            idx = D[i][1]
            if ans[idx] == -1:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# for test
# sys.stdin = open('sample.txt') 

# main
N, Q = R()
STX = [R() for _ in range(N)]
STX.sort(key=itemgetter(2))

D = [int(r()) for _ in range(Q)]
Stopped = [-1] * Q
ans = [-1] * Q

for s, t, x in STX:
    left = s - x
    right = t - x
    a = bisect_left(D, left)
    b = bisect_left(D, right)
    while a < b:
        if Stopped[a] == -1:
            ans[a] = x
            Stopped[a] = right
            a += 1
        else:
            a = Stopped[a]

for i in ans:
    print(i)

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append / extend
Dic[x].append(y)
# for
for k, v in Dic.items():
"""

# if __name__ == '__main__':
#     main()

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1 for _ in range(query[-1]+1)]

   # for s, t, x in works:
   #     start = s-x if s-x >= 0 else 0
   #     end = t-x if t-x >= 0 else 0
   #     for p in range(start, min(end, len(L))):
  #          L[p] = x
 # for q in query:

    print(0)


solve()

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    #L = [-1]*(max(query)+1)

   # for s, t, x in works:
   #     start = s-x if s-x >= 0 else 0
   #     end = t-x if t-x >= 0 else 0
   #     for p in range(start, min(end, len(L))):
  #          L[p] = x
 # for q in query:
    print(0)


solve()

Submission status: Wrong Answer

Solution code:
from math import ceil, log2
import sys


input = sys.stdin.readline
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import ceil, log2


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break


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

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
event=[]
for _ in range(n):
  s,t,x=map(int,input().split())
  event.append([s-x,1,x])
  event.append([t-x,-1,x])
event=sorted(event,key=lambda x:x[0])
pos=[int(input()) for _ in range(q)]
sx=set()
p=0
m=-1
ans=[-1]*q
for s,f,x in event:
  if s>pos[p]:
    ans[p]=m
    p+=1
  if f==1:
    sx.add(x)
    if m==-1:
      m=x
    else:
      m=min(m,x)
  else:
    sx.remove(x)
    if m==x:
      if len(sx)==0:
        m=-1
      else:
        m=min(list(sx))
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    a = [s - x, t - x, x] #イベント
    E.append(a)
E.sort(key = lambda x: x[2])
D = []
for i in range(Q):
    D.append(int(input()))

ans = [-1]*Q

for e in E:
    l = bs.bisect_left(D, e[0])
    r = bs.bisect_right(D, e[1])
    for i in range(l, r):
        if ans[i] == -1:
            ans[i] = e[2]
        else:
            pass
    
[print(i) for i in ans]

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import heapq as hp
#import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    app = [s - x, -1, x] #追加イベント
    rem = [t - x, -2, x] #削除イベント
    E.append(app)
    E.append(rem)
for i in range(Q):
    d = [int(input()), i, -1]
    E.append(d)
E.sort(key = lambda x:x[0])

ans = []
stopX = []

for e in E:
    if e[1] == -1:
        hp.heappush(stopX,e[2])
    elif e[1] == -2:
        stopX.remove(e[2])
    else:
        if len(stopX) != 0:
            ans.append(stopX[0])
        else:
            ans.append(-1)
[print(i) for i in ans]

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
  Events.append((max(0,s-x), 1, x))
  Events.append((max(0,t-x), -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events = Events[::-1] #降順にする reverseを使うのは、「ひっくり返した状態で」安定じゃないとイベントの入力順がズレてエラーが出るため。reverseを使うと、キーが重複している場合は元の順番を保ってしまう（ひっくり返すと、キーが重複している部分に限っては元の順番と反対になってしまい、「存在しない値を集合からひこうとする」というエラーになる）

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
minstop = 10**9+1
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = nextevent
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
      minstop = min(c, minstop)
    else: #座標xの通行止めが解除される
      try:
          nowkeptout.remove(c)
      except: print("aaaaa")
      if c==minstop and nowkeptout: minstop = min(nowkeptout)
      elif not nowkeptout: minstop = 10**9+1
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 1, 1) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(minstop)
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
  Events.append((max(0,s-x), 1, x))
  Events.append((max(0,t-x), -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events = Events[::-1] #降順にする reverseを使うのは、「ひっくり返した状態で」安定じゃないとイベントの入力順がズレてエラーが出るため。reverseを使うと、キーが重複している場合は元の順番を保ってしまう（ひっくり返すと、キーが重複している部分に限っては元の順番と反対になってしまい、「存在しない値を集合からひこうとする」というエラーになる）

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
minstop = 10**9+1
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    try:
      a, b, c = nextevent
      if b==1: #座標xが通行止めになる
        nowkeptout.add(c)
        minstop = min(c, minstop)
      else: #座標xの通行止めが解除される
        nowkeptout.remove(c)
        if c==minstop and nowkeptout: minstop = min(nowkeptout)
        elif not nowkeptout: minstop = 10**9+1
    except:print("aaaaa")
    
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 1, 1) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(minstop)
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Wrong Answer

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
  Events.append((max(0,s-x), 1, x))
  Events.append((max(0,t-x), -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events = Events[::-1] #降順にする reverseを使うのは、「ひっくり返した状態で」安定じゃないとイベントの入力順がズレてエラーが出るため。reverseを使うと、キーが重複している場合は元の順番を保ってしまう（ひっくり返すと、キーが重複している部分に限っては元の順番と反対になってしまい、「存在しない値を集合からひこうとする」というエラーになる）

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
minstop = 10**9+1
for d in Ds:
  try:
    #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
    #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
    while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
      a, b, c = nextevent
      if b==1: #座標xが通行止めになる
        nowkeptout.add(c)
        minstop = min(c, minstop)
      else: #座標xの通行止めが解除される
        nowkeptout.remove(c)
        if c==minstop and nowkeptout: minstop = min(nowkeptout)
        elif not nowkeptout: minstop = 10**9+1
      try: nextevent = Events.pop()
      except:
        nextevent = (10**9+1, 1, 1) #要素がなくなったらもう処理が起きないようにする
        break
    #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
    #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
    #値が入っていなければ歩き続けるので、-1にする
    if nowkeptout: Anss.append(minstop)
    else: Anss.append(-1)
  except:
    print("aaaaaa")
for ans in Anss:
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
    events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
m = float('inf')
for e in events:
    if e[1] == 0:
        block.remove(e[2])
        if m == e[2]:
            if block:
                m = min(block)
            else:
                m = float('inf')
    elif e[1] == 1:
        block.add(e[2])
        m = min(m, e[2])
    else:
        if block:
            if m == float('inf'):
                ans[e[2]] = -1
            else:
                ans[e[2]] = m
print(ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
    events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
for e in events:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            ans[e[2]] = min(block)
print(ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import collections, sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for d in D:
    events += [[d, 2]]
events.sort()
block = set()
ans = []
for e in events:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            #ans += [min(block)]
            1
        else:
            #ans += [-1]
            1

Submission status: Wrong Answer

Solution code:
def bisect(val):
  l=-1
  r=q
  while 1:
    if r-l==1:
      break
    mid=int((l+r)//2)
    if pos[mid]>=val:
      r=mid
    else:
      l=mid
  return r

n,q=map(int,input().split())
work=[list(map(int,input().split())) for _ in range(n)]
work=sorted(work,key=lambda x:x[2])
pos=[int(input()) for _ in range(q)]
ans=[-1]*q
checked=[-1]*q
for s,t,x in work:
  l=bisect(s-x)
  r=bisect(t-x)
  while l<r:
    if checked[l]==-1:
      checked[l]=r
      ans[l]=x
    else:
      l=checked[l]
    l+=1
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
from subprocess import*
call(('pypy3','-c',"""
def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l//=2
            r//=2
    a=[]
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        a.append(-(s==I)or s)
    print('\n'.join(map(str,a)))
main()
"""))

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, Q = map(int, input().split())
S, T, X = [0] * N, [0] * N, [0] * N
work = []

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

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

work.sort()
ans = [-1] * Q
skip = [-1] * Q

for i in range(N):
	left = bisect.bisect_left(D, work[i][1])
	right = bisect.bisect_left(D, work[i][2])
	
	while left < right:
		if skip[left] == -1:
			skip[left] = right
			ans[left] = work[i][0]
		else:
			left = skip[left]
			
		left += 1
		
for i in ans:
	print(i)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, Q = map(int, input().split())
S, T, X = [0] * N, [0] * N, [0] * N

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

event = [] #工事と人を１つのリストで管理: (時間, 出来事の種類, [工事の位置])
#出来事の種類: (0: 工事の終了、1: 工事の開始、2: 人)
working = [] #現在行われている工事のリスト
n = 0 #現在行われている工事の数

for i in range(Q):
	event.append((D[i], 2))
	
for i in range(N):
	bisect.insort(event, (S[i] - X[i] - 0.5, 1, X[i]))
	bisect.insort(event, (T[i] - X[i] - 0.5, 0, X[i]))
	
for l in event:
	if l[1] == 1:
		bisect.insort(working, l[2])
		n += 1
	elif l[1] == 0:
		del working[bisect.bisect(working, l[2]) - 1]
		n -= 1
	else:
		if n > 0:
			print(working[0])
		else:
			print(-2)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, Q = map(int, input().split())
S, T, X = [0] * N, [0] * N, [0] * N

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

event = [] #工事と人を１つのリストで管理: (時間, 出来事の種類, [工事の位置])
#出来事の種類: (0: 工事の終了、1: 工事の開始、2: 人)
working = [] #現在行われている工事のリスト
n = 0 #現在行われている工事の数

for i in range(Q):
	event.append((D[i], 2))
	
for i in range(N):
	bisect.insort(event, (S[i] - X[i] - 0.5, 1, X[i]))
	bisect.insort(event, (T[i] - X[i] - 0.5, 0, X[i]))
	
for l in event:
	if l[1] == 1:
		bisect.insort(working, l[2])
		n += 1
	elif l[1] == 0:
		#del working[bisect.bisect(working, l[2]) - 1]
		n -= 1
	else:
		if n > 0:
			print(working[0])
		else:
			print(-1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
stx.sort(key=lambda x: x[2])
d = [int(input()) for _ in range(q)]

res = [-1] * q
for s, t, x in stx:
    l = bisect_left(d, s-x)
    r = bisect_left(d, t-x)
    for i in range(l, r):
        if res[i] != -1:
            break
        res[i] = x
    for i in range(r-1, l-1, -1):
        if res[i] != -1:
            break
        res[i] = x
print(*res)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
stx.sort(key=lambda x: x[2])
d = [int(input()) for _ in range(q)]

res = [-1] * q
for s, t, x in stx:
    l = bisect_left(d, s-x)
    r = bisect_left(d, t-x)
    for i in range(l, r):
        if res[i] != -1:
            break
        res[i] = x
    for i in range(r-1, l-1, -1):
        if res[i] != -1:
            break
        res[i] = x
print(res)

Submission status: Wrong Answer

Solution code:
N,Q = list(map(int,input().split(" ")))
kojis = []
hitos = {}

ans = [-1] * Q

for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    l = S -X
    r = T -X
    kojis.append((l,r,X))
kojis.sort(key=lambda x:x[2])


for i in range(Q):
    t = int(input())
    hitos[t] = (t,i)

for koji in kojis:
    rem = []
    l,r,x = koji
    for i,hito in enumerate(hitos.values()):
        hitoTime,hitoNum = hito
        if l <= hitoTime and hitoTime < r:
            ans[hitoNum] = x
            rem.append(hitoTime)
        elif r <= hitoTime:
            break

    for i in rem:
        hitos.pop(i)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Jun 13 14:27:40 2019

@author: YudNK
"""

N, Q = map(int, input().split())
X = []
D = []
for i in range(N):
    l = [int(j) for j in input().split()]
    X.append(l)
X.sort(key = lambda x:x[2])
for j in range(Q):
    D.append(int(input()))
    
result = []
for l in X:
    count = 0
    while D[count] != D[-1]:
        if D[count] >= l[1] - l[2]:
            break
        elif D[count] < l[0] - l[2]:
            count += 1
        else:
            result.append([D[count],l[2]])
            D.remove(D[count])
for k in D:
    result.append([k,-1])
result.sort()
[print(i[1]) for i in result]

Submission status: Wrong Answer

Solution code:
import sys 

def check_work(D, work_list):
    value_list = []
    for work in work_list:
        start, end, X = work
        if start <= D <= end:
            value_list.append(X)
    if value_list == []:
        print(-1)
    else:
        print(min(value_list))
          
def main():
    N, Q = map(int, input().split())
    work_list = []
    for n in range(N):
        S, T, X = map(int, input().split())
        work_list.append([X-T+1, X-S, X])
    print(work_list)
    for q in range(Q):
        D = int(input())
        check_work(-D, work_list)
main()