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:

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

S,T,X = [],[],[]

Ev = []
for _ in range(N):
  s,t,x = list(map(int, input().split())) 
  Ev.append((s-x,True,x))
  Ev.append((t-x,False,x))
"""
2 5 6
5 -1
4 2
3 3
2 4
1 5
0 -1
"""
Ev.sort()
#print(Ev)
Closed = set()
#Query = []
eidx = 0
for i in range(Q):
  # dはsortedでinputされる。
  d = int(input())
  #Query.append(d)
  while eidx < 2*N and Ev[eidx][0] <= d:
    #pop
    t,e,x = Ev[eidx]
    eidx += 1
    if e:
      Closed.add(x)
    else:
      Closed.remove(x)
  if Closed and d <= min(Closed):
    print(min(Closed))
  else:
    print(-1)

Submission status: Wrong Answer

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


def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, x))
        key.append((r, x))

    key.sort()
    judge = []
    now = set()
    already = dict()
    D_search = []
    
    for i in range(n*2):
        s, x = key[i]
        if x in now:
            now.discard(x)
            if x in already:
                already[x] += 1
            else:
                already[x] = 1
        else:
            now = now.union({x})
            heappush(judge, x)
        
        if now:
            while D_search:
                if judge[0] in already and already[judge[0]] > 0:
                    already[judge[0]] -= 1
                    heappop(judge)
                else:
                    break
            D_search.append((s, judge[0]))
        else:
            while judge:
                heappop(judge)
            already = dict()
            D_search.append((s, -1))
    
    D_search.sort()
    
    search = []
    sub = -1
    for (s, x) in D_search:
        if sub != s:
            search.append((s, x))
        sub = s
    
    size = len(search)
    index = 0
    for i in range(q):
        d = int(input())
        while index < size-1:
            if search[index+1][0] <= d:
                index += 1
            else:
                break
        
        print(search[index][1])

        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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


def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, x))
        key.append((r, x))

    key.sort()
    judge = []
    now = set()
    already = dict()
    D_search = []
    for i in range(n*2):
        s, x = key[i]
        if x in now:
            now.discard(x)
            if x in already:
                already[x] += 1
            else:
                already[x] = 1
        else:
            now = now.union({x})
            heappush(judge, x)
        
        if now:
            while D_search:
                if judge[0] in already and already[judge[0]] > 0:
                    already[judge[0]] -= 1
                    heappop(judge)
                else:
                    break
            D_search.append((s, judge[0]))
        else:
            D_search.append((s, -1))
    
    D_search.sort()
    
    search = []
    sub = -1
    for (s, x) in D_search:
        if sub != s:
            search.append((s, x))
        sub = s
    
    size = len(search)
    index = 0
    for i in range(q):
        d = int(input())
        while index < size-1:
            if search[index+1][0] <= d:
                index += 1
            else:
                break
        
        print(search[index][1])

        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class DualSegmentTree():

    def __init__(self, n, op, e):
        """
        :param n: 配列の要素数
        :param op: 作用素（モノイド＝結合則＋単位元存在）
        :param e:  単位元
        """
        self.n = n
        self.op = op
        self.e = e
        self.depth = (self.n - 1).bit_length()
        self.size = 1 << self.depth
        self.lazy = [self.e] * ((self.size << 1) + 1)

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.lazy[self.size + i] = array[i]

    def update(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        l += self.size
        r += self.size
        self.propagate(l>>(l&-l))
        self.propagate((r>>(r&-r))-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.op(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.op(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1

    def propagate(self, i):
        """
        根から葉に伝搬させる。可換モノイドの場合は更新時の伝搬をサボれる。　（ O(logN) ）
        """
        for k in range(i.bit_length()-1, 0,-1):
            x = i>>k
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)|1] = self.op(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.op(self.lazy[x], self.lazy[x<<1])
            self.lazy[x] = self.e

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate(i)
        return self.lazy[i]

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)|1] = self.op(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.op(self.lazy[x], self.lazy[x<<1])
            self.lazy[x] = self.e
        for a in self.lazy[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)|1] = self.op(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.op(self.lazy[x], self.lazy[x<<1])
            self.lazy[x] = self.e
        return str(self.lazy[self.size:self.size + self.n])

##################################################################################################################
import sys
from bisect import *
input = sys.stdin.readline

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

e = -1
op = lambda x, y: x if x != e else y
st = DualSegmentTree(Q, op, e)

Qu = [list(map(int, input().split())) for _ in range(N)]
Qu.sort(key=lambda x:x[2], reverse=True)

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

for q in Qu:
    S, T, X = q
    L = bisect_left(D,S-X)
    R = bisect_left(D,T-X)
    st.update(L, R, X)
print(*st, sep="\n")

Submission status: Wrong Answer

Solution code:
class DualSegmentTree():

    def __init__(self, n, op, e):
        """
        :param n: 配列の要素数
        :param op: 作用素（モノイド＝結合則＋単位元存在）
        :param e:  単位元
        """
        self.n = n
        self.op = op
        self.e = e
        self.depth = (self.n - 1).bit_length()
        self.size = 1 << self.depth
        self.lazy = [self.e] * ((self.size << 1) + 1)

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.lazy[self.size + i] = array[i]

    def update(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-l)
        self.propagate(l0)
        self.propagate(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.op(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.op(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1

    def propagate(self, i):
        """
        根から葉に伝搬させる。可換モノイドの場合は更新時の伝搬をサボれる。　（ O(logN) ）
        """
        for k in range(self.depth,0,-1):
            x = i>>k
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)|1] = self.op(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.op(self.lazy[x], self.lazy[x<<1])
            self.lazy[x] = self.e

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate(i)
        return self.lazy[i]

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)|1] = self.op(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.op(self.lazy[x], self.lazy[x<<1])
            self.lazy[x] = self.e
        for a in self.lazy[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.e:
                continue
            self.lazy[(x<<1)|1] = self.op(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.op(self.lazy[x], self.lazy[x<<1])
            self.lazy[x] = self.e
        return str(self.lazy[self.size:self.size + self.n])

##################################################################################################################
import sys
from bisect import *
input = sys.stdin.readline

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

e = -1
op = lambda x, y: x if x != e else y
st = DualSegmentTree(Q, op, e)

Qu = [list(map(int, input().split())) for _ in range(N)]
Qu.sort(key=lambda x:x[2], reverse=True)

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

for q in Qu:
    S, T, X = q
    L = bisect_left(D,S-X)
    R = bisect_left(D,T-X)
    st.update(L, R, X)
print(*st, sep="\n")

Submission status: Wrong Answer

Solution code:
class DualSegmentTree():

    def __init__(self, n, op, e):
        """
        :param n: 配列の要素数
        :param op: 作用素（モノイド＝結合則＋単位元存在）
        :param e:  単位元
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()
        self.lazy = [self.e] * (self.size << 1)

    def update(self, l, r, x):
        """
        半開区間 [l, r) の値を x に更新 （ 0-indexed ）　（ O(logN) ）
        """
        l += (self.size - 1)
        r += (self.size - 1)
        self.propagate(l)
        self.propagate(r-1)
        while l < r:
            if r&1 == 0:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.op(x, self.lazy[r])
            if l&1 == 0:
                self.lazy[l] = self.op(x, self.lazy[l])
                l += 1
            l = (l - 1) // 2
            r = (r - 1) // 2

    def propagate(self, i):
        """
        根から葉に伝搬させる。可換モノイドの場合は更新時の伝搬をサボれる。　（ O(logN) ）
        """
        tmp = []
        while i>0:
            i -= 1
            i >>= 1
            tmp.append(i)
        for x in reversed(tmp):
            if self.lazy[x] == self.e:
                continue
            self.lazy[2*x+1] = self.op(self.lazy[x], self.lazy[2*x+1])
            self.lazy[2*x+2] = self.op(self.lazy[x], self.lazy[2*x+2])
            self.lazy[x] = self.e

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += (self.size - 1)
        self.propagate(i)
        return self.lazy[i]

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(self.size-1):
            if self.lazy[x] == self.e:
                continue
            self.lazy[2*x+1] = self.op(self.lazy[x], self.lazy[2*x+1])
            self.lazy[2*x+2] = self.op(self.lazy[x], self.lazy[2*x+2])
            self.lazy[x] = self.e
        for a in self.lazy[self.size-1:self.size-1+self.n]:
            yield a

    def __str__(self):
        for x in range(self.size-1):
            if self.lazy[x] == self.e:
                continue
            self.lazy[2*x+1] = self.op(self.lazy[x], self.lazy[2*x+1])
            self.lazy[2*x+2] = self.op(self.lazy[x], self.lazy[2*x+2])
            self.lazy[x] = self.e
        return str(self.lazy[self.size-1:self.size-1 + self.n])

##################################################################################################################
import sys
from bisect import *
input = sys.stdin.readline

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

e = -1
op = lambda x, y: x if x != e else y
st = DualSegmentTree(Q, op, e)

Qu = [list(map(int, input().split())) for _ in range(N)]
Qu.sort(key=lambda x:x[2], reverse=True)

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

for q in Qu:
    S, T, X = q
    L = bisect_left(D,S-X)
    R = bisect_left(D,T-X)
    st.update(L, R, X)
print(st)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 各queryについてO(n)で答える
# 問題を言い換えると　　

# 地点Xに到着するのは時間 Di + Xの時
# S <= Di + X < Tとなる[S, T, N]がなければ通過できる
# SについてXの早い順にソートする

# 各Dについて、どのSまで通過できるかを各O(1)で答える？

N,Q = getNM()
# taskに
# 0:通行止め時間帯のスタート
# 1:通行止め時間帯のゴール
# 2:人
# を入れ、全部まとめて処理する
task = []

STX = [getList() for _ in range(N)]
for s, t, x in STX:
    task.append((t - x, 0, x)) # xで止まらなくなる
    task.append((s - x, 1, x)) # xで止まる

for i in range(Q):
    d = getN()
    task.append((d, 2, i)) # 止まる位置を答える
answer = [-1] * Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ
heapq.heapify(se_hp)

# 小さい時刻から順に見ていく
for a, b, c in task:
    # ゴール位置についての情報なら
    if b == 0:
        # とり除く
        se.remove(c)
    # スタートについての情報なら
    elif b == 1:
        se.add(c)
        heapq.heappush(se_hp, c)
    # 人についての情報なら
    else:
        # se_hpを抜き切るか、se_hpの最小値がseにある場合はエンド
        while se_hp and se_hp[0] not in se:
            heapq.heappop(se_hp)
        if se_hp:
            answer[c] = se_hp[0]
        else:
            answer[c] = -1

print(answer)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# N回工事
# Q人の人が同時に0をスタート
N, Q = getNM()
# 時刻[S, T]の間はXを通れない
S = [getList() for i in range(N)]
S = [[x - z, y - z - 1, z] for x, y, z in S]
# 時刻Diに出発する
D = getArray(Q)

# 各queryについてO(n)で答える
# 問題を言い換えると　　

# 地点Xに到着するのは時間 Di + Xの時
# S <= Di + X < Tとなる[S, T, N]がなければ通過できる
# SについてXの早い順にソートする

# 各Dについて、どのSまで通過できるかを各O(1)で答える？

S.sort(key = lambda i: i[2])

# [[1, 3, 2], [3, 4, 2], [7, 13, 10], [18, 20, 13]]について
# [1, 3, 2] -1 <= D <= 0であればヒット
# [3, 4, 2] 1 <= D <= 1であればヒット
# [7, 13, 10] -3 <= D <= 2であればヒット
# [18, 20, 13] 5 <= D <= 6であればヒット
# これらを一つにまとめてO(1)で答えられないか？

# Xが大きいため数直線上にはかけない
# 累積？
# ソートして貪欲？
# 最小値の左側にあれば関係ないし、最大値の右側にいても関係ない
# 二分探索使えばlogN
# ヒープキュー

mi_l = [0] * N
for i in range(N):
    if i >= 1 and S[i][0] < S[i - 1][0]:
        mi_l[i] = S[i - 1][0]
    else:
        mi_l[i] = S[i][0]

ma_l = [0] * N
for i in range(N):
    if i >= 1 and S[i][1] < S[i - 1][1]:
        ma_l[i] = S[i - 1][1]
    else:
        ma_l[i] = S[i][1]

# 修正
diff = min(min(mi_l), min(ma_l), min(D))
D = [i - diff for i in D]
mi_l = [i - diff for i in mi_l]
ma_l = [i - diff for i in ma_l]

for i in range(Q):
    ind_mi = bisect_left(mi_l, D[i] + 1)
    ind_ma = bisect_left(ma_l, D[i])
    if ind_mi > ind_ma:
        print(S[ind_ma][2])
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from heapq import heappop, heappush, heapify
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

'''
import random
N = 2*10**5
Q = 2*10**5
STX = []
for i in range(N):
    S,T = sorted([random.randint(0,10**9-1) for i in range(2)])
    if S == T:
        T += 1
    X = random.randint(1,10**9)
    STX.append([S,T,X])
D = sorted([random.randint(0,10*9) for i in range(Q)])
'''

inf = 10**15
PFXS = [(s-x,True,x) for s,t,x in STX]
PFXT = [(t-x,False,x) for s,t,x in STX]
PFX = PFXS + PFXT
PFX.append((-inf,True,inf))
PFX.append((inf,False,inf))
PFX.sort()

addq = [inf]
delq = [inf+1]
iterD = iter(D)

d = next(iterD)
for p,f,x in PFX:
    while d < p:
        ans = addq[0] if not addq[0] == inf else -1
        #print(ans)
        try:
            d = next(iterD)
        except:
            exit()
    if f:
        heappush(addq, x)
    else:
        heappush(delq, x)
    while addq[0] == delq[0]:
        heappop(addq)
        heappop(delq)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from heapq import heappop, heappush, heapify
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

PFX = [[(s-x,True,x),(t-x,False,x)] for s,t,x in STX]
PFX = sorted(sum(PFX, []))

inf = 10**15
D += [-inf]
addq = [inf]
delq = [inf+1]
iterD = iter(D)

d = next(iterD)
for p,f,x in PFX:

    if d < p:
        d = next(iterD)
        ans = addq[0] if not addq[0] == inf else -1
        print(ans)

    if f:
        heappush(addq, x)
    else:
        heappush(delq, x)
    while addq[0] == delq[0]:
        heappop(addq)
        heappop(delq)

for d in iterD:
    print(-1)

Submission status: Wrong Answer

Solution code:
# roadwork
import heapq
N, Q = map(int, input().split())
que = []
D = []
heapq.heapify(D)

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

for i in range(Q):
    d = int(input())
    que.append((d, i, -1, -1))
ans = [-1 for i in range(Q)]
que.sort(key=lambda x: x[0])
banned = [False for i in range(N)]
for place, querie, distance, index in que:
    if querie == "B":
        heapq.heappush(D, (distance, index))
        continue
    elif querie == "E":
        banned[index] = True
        continue
    else:
        if not D:
            continue
        else:
            flag = True
            while D and flag:
                di, ind = heapq.heappop(D)
                if banned[ind]:
                    continue
                else:
                    ans[querie] = di
                    flag = False
for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
# roadwork
import heapq
N, Q = map(int, input().split())
que = []
D = []
heapq.heapify(D)

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

for i in range(Q):
    d = int(input())
    que.append((d, i, -1, -1))
ans = [-1 for i in range(Q)]
que.sort(key=lambda x: x[0])
banned = [False for i in range(N)]
for place, querie, distance, index in que:
    if querie == "B":
        heapq.heappush(D, (distance, index))
    elif querie == "E":
        banned[index] = True
    else:
        if not D:
            pass
        else:
            flag = True
            while D and flag:
                distance, ind = heapq.heappop(D)
                if banned[ind]:
                    continue
                else:
                    ans[querie] = distance
                    flag = False
for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    a = max(0, s-x)
    b = max(0, t-x)
    STX.append([x, a, b])
    vals.add(a)
    vals.add(b)
D = []
for _ in range(Q):
    d = int(input())
    D.append(d)
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort()
priority = 0 
for x,s,t in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

# import heapq
# cur = -1
# cur_priority = 10**9
# que = [[cur_priority, cur]]
# valid_priority = [True]*(N+1)
# for i in range(L+1):
#     for f,p,x in  imos[i]:
#         if f:
#             heapq.heappush(que, [p, x])
#         else:
#             valid_priority[p] = False
    
#     while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
#         heapq.heappop(que)
#     mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append([x, max(0,s-x), max(0,t-x)])
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort()
priority = 0 
for x,s,t in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

# import heapq
# cur = -1
# cur_priority = 10**9
# que = [[cur_priority, cur]]
# valid_priority = [True]*(N+1)
# for i in range(L+1):
#     for f,p,x in  imos[i]:
#         if f:
#             heapq.heappush(que, [p, x])
#         else:
#             valid_priority[p] = False
    
#     while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
#         heapq.heappop(que)
#     mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append([max(0,s-x), max(0,t-x), x])
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

# import heapq
# cur = -1
# cur_priority = 10**9
# que = [[cur_priority, cur]]
# valid_priority = [True]*(N+1)
# for i in range(L+1):
#     for f,p,x in  imos[i]:
#         if f:
#             heapq.heappush(que, [p, x])
#         else:
#             valid_priority[p] = False
    
#     while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
#         heapq.heappop(que)
#     mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append([max(0,s-x), max(0,t-x), x])
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+10)
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    for i in range(s1, t1):
        if mapping[i]==-1:
            mapping[i] = x
    
for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])

Submission status: Wrong Answer

Solution code:
# Solution using a lazy segment tree

from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.lazy = [None] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        return self.tree[self.N-1:self.n+self.N-1]

    def getindex(self, l, r):
        l = (l + self.N)
        r = (r + self.N)
        lm = l // (l & -l) >> 1
        rm = r // (r & -r) >> 1
        while r-l > 0:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l = l >> 1
            r = r >> 1
        while l:
            yield l
            l = l >> 1

    def propagates(self, *indices):
        for i in reversed(indices):
            i -= 1
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i+1] = self.tree[2*i+1] = v >> 1
            self.lazy[2*i+2] = self.tree[2*i+2] = v >> 1
            self.lazy[i] = None

    def update(self, p, q, x):
        if p == q:
            return None
        indices = tuple(self.getindex(p, q))
        self.propagates(*indices)
        p += self.N-1
        q += self.N-2
        while q-p > 0:
            if p % 2 == 0:
                self.lazy[p] = self.tree[p] = x
            if q % 2 == 1:
                self.lazy[q] = self.tree[q] = x
            p = p//2
            q = q//2 - 1
            x <<= 1
        if p == q:
            self.lazy[p] = self.tree[p] = x
        for i in indices:
            i -= 1
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        self.propagates(*self.getindex(p, q))
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 0:
            if p % 2 == 0:
                res = self.opr(res, self.tree[p])
            if q % 2 == 1:
                res = self.opr(res, self.tree[q])
            p = p//2
            q = q//2 - 1
        if p == q:
            res = self.opr(res, self.tree[p])
        return res


n, q = map(int, input().split())

Works = []
for _ in range(n):
    s, t, x = map(int, input().split())
    Works.append((s, t, x))
Works = sorted(Works, key=lambda w: -w[2])

People = []
for _ in range(q):
    People.append(int(input()))

ST = SegmentTree([-1]*q)

for s, t, x in Works:
    left = bisect_left(People, s-x)
    right = bisect_left(People, t-x)
    ST.update(left, right, x)

for x in ST.values():
    print(x)

Submission status: Wrong Answer

Solution code:
import heapq
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))

for _ in range(q):
    d = int(input())
    event.append((d, 2, 0))

event.sort(key=lambda x: (x[0], x[1]))
now = []
memo = set()

tmp = 0
print(event)
for i, (t, flg, x) in enumerate(event):
    if flg == -1:
        memo.remove(x)
    elif flg == 1:
        heapq.heappush(now, x)
        memo.add(x)
    else:
        while len(now) > 0 and now[0] not in memo:
            heapq.heappop(now)
        if len(now) > 0:
            print(now[0])
        else:
            print(-1)