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:
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()
now = []
fin = set()

tmp = 0
for i, (t, flg, x) in enumerate(event):
    if flg == -1:
        fin.add(x)
    elif flg == 1:
        heapq.heappush(now, x)

    else:
        while len(now) > 0 and now[0] in fin:
            heapq.heappop(now)
        if len(now) > 0:
            print(now[0])
        else:
            print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
import heapq

INF = float("inf")


class ErasableHeap(object):
    # https://qiita.com/Salmonize/items/638da118cd621d2628d1
    def __init__(self):
        self.data = []
        self.event = []

    def push(self, x):
        return heapq.heappush(self.data, x)

    def erase(self, x):
        return heapq.heappush(self.event, x)

    def _check(self):
        while self.event and\
                self.data[0] == self.event[0]:
            heapq.heappop(self.data)
            heapq.heappop(self.event)

    def front(self):
        self._check()
        return self.data[0]

    def pop(self):
        self.check()
        return heapq.heappop(self.data)

    def __len__(self):
        self._check()
        return len(self.data)


def main():
    N, Q = map(int, input().split())
    XST = [0]*N
    for i in range(N):
        s, t, x = map(int, input().split())
        XST[i] = (x, s-x, t-x)
    D = [0]*Q
    for i in range(Q):
        D[i] = int(input())
    event = []
    for x, s, t in XST:
        event.append((s, 1, x))
        event.append((t, -1, x))

    event.sort()

    head = 0
    stack = ErasableHeap()
    for t, p, x in event:
        if head >= Q:
            return
        while D[head] < t:
            if len(stack) == 0:
                print(-1)
            else:
                print(stack.front())
            head += 1
            if head >= Q:
                return
        if p == 1:
            stack.push(x)
        else:
            stack.erase(x)
    if len(stack) == 0:
        print(-1)
    else:
        print(stack.front())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
INF = float("inf")


def main():
    N, Q = map(int, input().split())
    XST = [0]*N
    for i in range(N):
        s, t, x = map(int, input().split())
        XST[i] = (x, s-x, t-x)
    D = [0]*Q
    for i in range(Q):
        D[i] = int(input())
    event = []
    for x, s, t in XST:
        event.append((s, 1, x))
        event.append((t, -1, x))

    event.sort()
    head = 0
    stack = set()
    for t, p, x in event:
        if head >= Q:
            return
        while D[head] < t:
            if len(stack) == 0:
                print(-1)
            else:
                print(min(stack))
            head += 1
            if head >= Q:
                return
        if p == 1:
            stack |= {x}
        else:
            stack -= {x}
    if len(stack) == 0:
        print(-1)
    else:
        print(min(stack))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
INF = float("inf")


def main():
    N, Q = map(int, input().split())
    XST = [0]*N
    for i in range(N):
        s, t, x = map(int, input().split())
        XST[i] = (x, s-x, t-x)
    D = [0]*Q
    for i in range(Q):
        D[i] = int(input())
    event = []
    for x, s, t in XST:
        event.append((s, 1, x))
        event.append((t, -1, x))

    event.sort()
    head = 0
    stack = set()
    for t, p, x in event:
        if head >= Q:
            return
        if D[head] < t:
            if len(stack) == 0:
                print(-1)
            else:
                print(min(stack))
            head += 1
        if p == 1:
            stack |= {x}
        else:
            stack -= {x}
    if len(stack) == 0:
        print(-1)
    else:
        print(min(stack))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, Q = MAP()

event = [None]*(2*N+Q)
Xl = [0]*N
for i in range(N):
    S, T, X = MAP()
    event[2*i] = (S-X, 1, X)
    event[2*i+1] = (T-X, 0, X)
    Xl[i] = X

t = 2*N
for i in range(Q):
    D = INT()
    event[t+i] = (D, 2, 0)


event.sort()
p = []
q = set()
for t, c, x in event:
    if c == 0:
        q.add(x)
    elif c == 1:
        heappush(p, x)
    else:
        while q and p[0] in q:
            q.remove(p[0])
            heappop(p)
            
        print(-1 if not p else p[0])

Submission status: Wrong Answer

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
STX.sort(key=lambda x: x[2], reverse=True)
event = []
for s, t, x in STX:
    s = max(0, s-x)
    t = max(0, t-x)
    event.append((s, 0, x))
    event.append((t, -1, x))

answer = [None] * Q
for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort(key=lambda x: [x[0], x[1]])
cur = []
used = set()
for a, b, c in event:
    if b == 0:
        if c in used:
            used.remove(c)
        heappush(cur, c)
    elif b == -1:
        used.add(c)
    elif b == 1:
        while cur and cur[0] in used:
            heappop(cur)
        if cur:
            answer[c] = cur[0]
        else:
            answer[c] = -1

print('\n'.join(map(str, answer)))
# 19

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  # 1-indexed
    def __init__(self,n):  # 1~nを要素として持ちうる。
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  # kを木に加える
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): # kを木から削除する
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  # 1~kの和
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  # k以上の最小要素
        x = self.sum(k-1)
        if x == self.sum(self.n):  # k以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k-1)なるpの右端 + 1が答え
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  # k以下の最大要素
        x = self.sum(k)
        if x == 0:  # k以下の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k)なるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  # k番目の要素出力
        if k > self.sum(self.n):  # k個以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = kなるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

stx  = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    stx.append([s-x,x,1])
    stx.append([t-x,x,0])

b,d = compress(X)
stx = [(x[0],d[x[1]],x[2]) for x in stx]
heapq.heapify(stx)

ans = []
avl = AVL_like_BIT(len(d))
for i in range(q):
    D = readint()
    a = 0
    while stx:
        a = heapq.heappop(stx)
        if a[0]<=D:
            if a[2]:
                avl.add(a[1])
            else:
                avl.delete(a[1])
        else:
            break
    ans.append(avl.lower_bound(0))
    if a:
        if a[2]:
            avl.add(a[1])
        else:
            avl.delete(a[1])

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush
from bisect import bisect_left

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]
INF = 10 ** 18
START = 1
END = 0

tfdi = []
for i, (s, t, x) in enumerate(stx):
    t_start = max(0, s - x)
    t_end = max(0, t - x)
    if t_end == 0:
        continue

    tfdi.append([t_start, START, x, i])
    tfdi.append([t_end, END, x, i])

tfdi.append([INF, START, INF, -1])
tfdi.sort()

hp = [[INF, -1]]
ts = []
dists = []
t_prev = -1
passed = set()
for t, f, d, i in tfdi:
    if t != t_prev:
        ts.append(t_prev)
        while hp[0][1] in passed:
            heappop(hp)

        dists.append(hp[0][0])

    if f == START:
        heappush(hp, [d, i])
    else:
        passed.add(i)

    t_prev = t

dists.append(INF)

for d in ds:
    i = bisect_left(ts, d)
    ans = dists[i]
    if ans == INF:
        ans = -1
    print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,q = LI()
    stx = [LI() for _ in range(n)]
    da = [I() for _ in range(q)]

    q = []
    for s,t,x in stx:
        sx = s - x
        tx = t - x
        heapq.heappush(q, (sx, x, tx))

    t = []
    cx = inf
    ctx = inf
    c = 0
    while len(q):
        sx, x, tx = heapq.heappop(q)
        # print("x", sx,x,tx)
        # print("q", q)
        # print("t", t)
        if sx > ctx:
            t.append((sx-1, cx))
            cx = x
            ctx = tx
        elif cx > x:
            if ctx > tx:
                heapq.heappush(q, (tx+1, cx, ctx))
            t.append((sx-1, cx))
            cx = x
            ctx = tx
        elif tx > ctx:
            heapq.heappush(q, (ctx+1, x, tx))

    t.append((inf, inf))
    # print("t", t)

    r = []
    for d in da:
        i = bisect.bisect_left(t, (d+1, -1))
        # print("d",d,i,t[i])
        u = t[i][1]
        if u == inf:
            r.append(-1)
        else:
            r.append(u)

    return JA(r, "\n")

print(main())

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

def segfun(x, y):
    return min(x, y)
ide_ele = float("inf")


class SegmentTree:
    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)
 
    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret


n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
# stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

import bisect

seg = SegmentTree(q, ide_ele, segfun)

for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    seg.update(l, r, x)

for i, j in enumerate(d):
    res = seg.query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
# stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

# N: 処理する区間の長さ

INF = 10**9 + 1
N = q
LV = (N-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
import bisect



for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, x)

for i, j in enumerate(d):
    res = query(i, i + 1)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            ans.append(x)
            flag = 0
            break
    if flag:
        ans.append(-1)
for i in ans:
    print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap




@mt
def slv(N, Q, STX, D):
    from heapq import heappop, heappush
    st = [[s-x, t-x, x] for s, t, x in STX]
    st.sort(reverse=True)
    q = []
    ans = []
    for d in D:
        while st and st[-1][0] <= d:
            _, r, x = st.pop()
            heappush(q, (r, x))
        while q and q[0][0] <= d:
            heappop(q)
        if q:
            ans.append(q[0][1])
        else:
            ans.append(-1)
    return ans






def main():
    N, Q = read_int_n()
    STX = [read_int_n() for _ in range(N)]
    D = [read_int() for _ in range(Q)]
    print(*slv(N, Q, STX, D), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = float('inf')
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    stx = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
    l = [int(stdin.readline().rstrip()) for _ in range(q)]

    N = len(l)
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [float('inf')]*(2*N0)
    lazy = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for s, t, x in stx:
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, x)

    for i in range(q):
        print(-1)

Submission status: Wrong Answer

Solution code:
INF = 1

class SegTree():
    def __init__(self, A):
        n_ = len(A)
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [INF for _ in range(2 * self.n - 1)]
        for k, a in enumerate(A):
            self.update(k, a)

    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])

    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = INF
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res


import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    stx = []
    for _ in range(n):
        s, t, x = map(int, input().split())
        stx.append(x*10**20 + s*10**10 + t)

    stx.sort()
    tmp = []
    for i in range(q):
        tmp.append(10**18 + 10**9 * -int(input()) + 1*10**6 + i)

    for i, z in enumerate(stx):
        x = z//10**20
        s = (z-x*10**20)//10**10
        t = z %10**10
        tmp.append(10**18 + 10**9 * (x-s) + 2*10**6 + i)
        tmp.append(10**18 + 10**9 * (x-t) + 0*10**6 + i)

    tmp.sort()
    exit(0)
    l = []
    d2i = {}
    memo = - 10 ** 10
    i_sg = -1

    for val, cat, index in tmp:
        if val > memo:
            i_sg += 1
            l.append(1)
        if cat == "B":
            l[i_sg]=val
            d2i[val] = (i_sg, index)
        elif cat == "A":
            stx[index][0] = i_sg
        else:
            stx[index][1] = i_sg

        memo = val
    sgt = SegTree(l + [1])
    ans = [-1] * q
    sgt_update = sgt.update
    sgt_query = sgt.query

    for s, t, x in stx:
        v = sgt_query(s+1, t+1)
        while v < 1:
            i_sg, i_d = d2i[v]
            ans[i_d] = x
            sgt_update(i_sg, 1)
            v = sgt_query(s+1, t+1)

    for ansi in ans:
        print(ansi)


main()

Submission status: Wrong Answer

Solution code:
INF = 1
class SegTree():
    def __init__(self, A):
        n_ = len(A)
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [INF for _ in range(2 * self.n - 1)]
        for k, a in enumerate(A):
            self.update(k, a)

    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])

    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = INF
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res


import sys
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    stx = [list(map(int, input().split())) for _ in range(n)]
    tmp = [(-int(input()), 1, i) for i in range(q)]
    stx.sort(key=lambda x:x[2])

    for i, (s, t, x) in enumerate(stx):
        tmp.append((x-s, 2, i))
        tmp.append((x-t, 0, i))

    exit(0)
    tmp.sort()
    l = []
    d2i = {}
    memo = - 10 ** 10
    i_sg = -1

    for val, cat, index in tmp:
        if val > memo:
            i_sg += 1
            l.append(1)
        if cat == "B":
            l[i_sg]=val
            d2i[val] = (i_sg, index)
        elif cat == "A":
            stx[index][0] = i_sg
        else:
            stx[index][1] = i_sg

        memo = val
    sgt = SegTree(l + [1])
    ans = [-1] * q
    sgt_update = sgt.update
    sgt_query = sgt.query

    for s, t, x in stx:
        v = sgt_query(s+1, t+1)
        while v < 1:
            i_sg, i_d = d2i[v]
            ans[i_d] = x
            sgt_update(i_sg, 1)
            v = sgt_query(s+1, t+1)

    for ansi in ans:
        print(ansi)


main()

Submission status: Wrong Answer

Solution code:
INF = 1
class SegTree():
    def __init__(self, A):
        n_ = len(A)
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [INF for _ in range(2 * self.n - 1)]
        for k, a in enumerate(A):
            self.update(k, a)

    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])

    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = INF
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res

def main():
    import sys
    input = sys.stdin.readline
    n, q = map(int, input().split())
    stx = []
    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append([s,t,x])
    tmp = []

    for i in range(q): tmp.append((-int(input()), "B", i))
    stx.sort(key=lambda x:x[2])
    for i, (s, t, x) in enumerate(stx):
        tmp.append((x-s, "C", i))
        tmp.append((x-t, "A", i))

    exit(0)
    tmp.sort()
    l = []
    d2i = {}
    memo = - 10 ** 10
    i_sg = -1

    for val, cat, index in tmp:
        if val > memo:
            i_sg += 1
            l.append(1)
        if cat == "B":
            l[i_sg]=val
            d2i[val] = (i_sg, index)
        elif cat == "A":
            stx[index][0] = i_sg
        else:
            stx[index][1] = i_sg

        memo = val
    sgt = SegTree(l + [1])
    ans = [-1] * q
    sgt_update = sgt.update
    sgt_query = sgt.query

    for s, t, x in stx:
        v = sgt_query(s+1, t+1)
        while v < 1:
            i_sg, i_d = d2i[v]
            ans[i_d] = x
            sgt_update(i_sg, 1)
            v = sgt_query(s+1, t+1)

    for ansi in ans:
        print(ansi)


main()

Submission status: Wrong Answer

Solution code:
INF = 1
class SegTree():
    def __init__(self, A):
        n_ = len(A)
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [INF for _ in range(2 * self.n - 1)]
        for k, a in enumerate(A):
            self.update(k, a)

    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])

    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = INF
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res

def main():
    import sys
    input = sys.stdin.readline
    n, q = map(int, input().split())
    stx = []
    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append([s,t,x])
    tmp = []
    for i in range(q): tmp.append([-int(input()), 1, i])
    stx.sort(key=lambda x:x[2])
    cnt = 0
    for z in stx:
        tmp.append([z[2]-z[0], 2, cnt])
        tmp.append([z[2]-z[1], 0, cnt])
        cnt += 1

    print(len(tmp))
    import time
    a = time.time()
    tmp.sort()
    print(time.time() - a)

    exit(0)
    l = []
    d2i = {}
    memo = - 10 ** 10
    i_sg = -1

    for val, cat, index in tmp:
        if val > memo:
            i_sg += 1
            l.append(1)
        if cat == "B":
            l[i_sg]=val
            d2i[val] = (i_sg, index)
        elif cat == "A":
            stx[index][0] = i_sg
        else:
            stx[index][1] = i_sg

        memo = val
    sgt = SegTree(l + [1])
    ans = [-1] * q
    sgt_update = sgt.update
    sgt_query = sgt.query

    for s, t, x in stx:
        v = sgt_query(s+1, t+1)
        while v < 1:
            i_sg, i_d = d2i[v]
            ans[i_d] = x
            sgt_update(i_sg, 1)
            v = sgt_query(s+1, t+1)

    for ansi in ans:
        print(ansi)


main()