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 sys
#from bisect import bisect_left as bl
input = sys.stdin.readline

n,Q=map(int,input().split())
xs,qs = [],[]
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x,t-x,x
    xs += [(s,1,x), (t,0,x)]
for _ in range(Q):
    qs.append(int(input()))

xs.sort()

h=set()
qi = 0
q = qs[qi]
for t,r,x in xs:
    if q < t:
        if h:
            c = -1
        else:
            c = -1
        while True:
            if q < t:
                print(c)
                Q-=1
                if Q:
                    qi += 1
                    q = qs[qi]
                    continue
                sys.exit()
            break
    if r:
        h.add(x)
    else:
        h.remove(x)
print("-1\n"*Q)

Submission status: Wrong Answer

Solution code:
import sys
#from bisect import bisect_left as bl
input = sys.stdin.readline

n,Q=map(int,input().split())
xs,qs = [],[]
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs += [(s,1,x), (t,0,x)]
for _ in range(Q):
    qs.append(int(input()))

xs.sort()

h=set()
qi = 0
q = qs[qi]
for t,r,x in xs:
    if q < t:
        if h:
            c = -1
        else:
            c = -1
        while True:
            if q < t:
                print(c)
                Q-=1
                if Q:
                    qi += 1
                    q = qs[qi]
                    continue
                sys.exit()
            break
    if r:
        h.add(x)
    else:
        h.remove(x)
print("-1\n"*Q)

Submission status: Wrong Answer

Solution code:
import sys
#from bisect import bisect_left as bl
input = sys.stdin.readline

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs += [(s,1,x), (t,0,x)]
    tmp.add(x)
for _ in range(Q):
    qs.append(int(input()))

xs.sort()

h=set()
qi = 0
q = qs[qi]
for t,r,x in xs:
    if q < t:
        if h:
            c = -1
        else:
            c = -1
        while True:
            if q < t:
                print(c)
                Q-=1
                if Q:
                    qi += 1
                    q = qs[qi]
                    continue
                sys.exit()
            break
    if r:
        h.add(x)
print("-1\n"*Q)

Submission status: Wrong Answer

Solution code:
import sys
#from bisect import bisect_left as bl
input = sys.stdin.readline

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs += [(s,1,x), (t,0,x)]
    tmp.add(x)
for _ in range(Q):
    qs.append(int(input()))

xs.sort()

h=set()
qi = 0
q = qs[qi]
for t,r,x in xs:
    if q < t:
        if h:
            c = -1
        else:
            c = -1
        while True:
            if q < t:
                print(c)
                Q-=1
                if Q:
                    qi += 1
                    q = qs[qi]
                    continue
                sys.exit()
            break
    if r:
        h.add(x)
    else:
        h.remove(x)
print("-1\n"*Q)

Submission status: Wrong Answer

Solution code:
import sys 
input = sys.stdin.readline
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
    tmp.add(x)
for _ in range(Q):
    qs.append(int(input()))

xs.sort()
tmp = list(tmp)
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

qi = 0
q = qs[qi]
XN = len(tmp)
st = SegTree([XN]*XN, XN, XN, min)
for t,r,x in xs:
    if q < t:
        c = 0
        while True:
            if q < t:
                if c != XN:
                    print(tmp[c])
                else:
                    print(-1)
                Q-=1
                if Q == 0:
                    break
                qi += 1
                q = qs[qi]
            else:
                break
#    print(t,r,x)
    if Q==0:
        break
print("-1\n"*Q)

Submission status: Wrong Answer

Solution code:
import sys 
input = sys.stdin.readline
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
    tmp.add(x)
for _ in range(Q):
    qs.append(int(input()))

xs.sort()
tmp = list(tmp)
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

qi = 0
q = qs[qi]
XN = len(tmp)
st = SegTree([XN]*XN, XN, XN, min)
for t,r,x in xs:
    if q < t:
        c = st.query(0,XN)
        while True:
            if q < t:
                if c != XN:
                    print(tmp[c])
                else:
                    print(-1)
                Q-=1
                if Q == 0:
                    break
                qi += 1
                q = qs[qi]
            else:
                break
#    print(t,r,x)
    if Q==0:
        break
print("-1\n"*Q)

Submission status: Wrong Answer

Solution code:
import sys 
input = sys.stdin.readline
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
    tmp.add(x)
xs.sort()
tmp = list(tmp)
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

q = int(input())
rs = set()
XN = len(tmp)
st = SegTree([XN]*XN, XN, XN, min)
for t,r,x in xs:
    if q < t:
        c = 1
#        c = st.query(0,XN)
        while True:
            if q < t:
                if c != XN:
                    print(tmp[c])
                else:
                    print(-1)
                Q-=1
                if Q == 0:
                    break
                q = int(input())
            else:
                break
#    print(t,r,x)
    if Q==0:
        break
#    if r:
#        st.update(x2i[x], x2i[x])
#    else:
#        st.update(x2i[x], XN)
print("-1\n"*Q)

Submission status: Wrong Answer

Solution code:
import sys 
input = sys.stdin.readline
# ABC140E
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n,Q=map(int,input().split())
xs,qs,tmp = [],[],set()
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
    tmp.add(x)
xs.sort()
tmp = list(tmp)
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

q = int(input())
rs = set()
XN = len(tmp)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,Q=map(int,input().split())
xs,qs = [],[]
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
xs.sort()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,Q=map(int,input().split())
xs,qs = [],[]
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
xs.sort()

Submission status: Wrong Answer

Solution code:
n,Q=map(int,input().split())
xs,qs = [],[]
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))

Submission status: Wrong Answer

Solution code:
n,Q=map(int,input().split())
xs,qs = [],[]
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
xs.sort()

Submission status: Wrong Answer

Solution code:
n,Q=map(int,input().split())
xs,qs = [],[]
for _ in range(n):
    s,t,x=map(int,input().split())
    s,t,x=s-x-0.5,t-x-0.5,x
    xs.append((s,1,x))
    xs.append((t,0,x))
xs.sort()
q = int(input())
print("-1\n"*Q)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SegTreeIndex:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値とindex(同値があった場合は一番左)を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max)
        :param init: 要素の初期値(単位元)
        """
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
        self.index = [self.init] * (n2 << 1)
        # 1段目(最下段)の初期化
        for i in range(n2):
            self.index[i+n2] = i
        # 2段目以降の初期化
        for i in range(n2-1, -1, -1):
            # 全部左の子の値に更新
            self.index[i] = self.index[i*2]

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            left, right = min(i, i^1), max(i, i^1)
            if self.func(self.tree[left], self.tree[right]) == self.tree[left]:
                self.tree[i >> 1] = self.tree[left]
                self.index[i >> 1] = self.index[left]
            else:
                self.tree[i >> 1] = self.tree[right]
                self.index[i >> 1] = self.index[right]
            i >>= 1
 
    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = (self.init, -1)
        while l < r:
            if r & 1:
                r -= 1
                res = self.func(s[0], self.tree[r])
                # 左との一致を優先する
                if res == s[0]:
                    pass
                else:
                    s = (self.tree[r], self.index[r])
            if l & 1:
                res = self.func(self.tree[l], s[0])
                # 左との一致を優先する
                if res == self.tree[l]:
                    s = (self.tree[l], self.index[l])
                else:
                    pass
                l += 1
            l >>= 1
            r >>= 1
        return s

N, Q = MAP()
ST = set()
X = set()
A = defaultdict(list)
for i in range(N):
    s, t, x = MAP()
    # 全ての工事を同じ時系列に持ってくる
    ST.add(s-x)
    ST.add(t-x)
    X.add(x)
    A[s-x].append((x, 0))
    A[t-x].append((x, 1))
D = LIST(Q)

# 座標圧縮
zip_x, unzip_x = {}, {}
X = sorted(X)
for i in range(len(X)):
    zip_x[X[i]] = i
    unzip_x[i] = X[i]

Dset = set(D)
S = sorted(ST|Dset)
B = {}
st = SegTreeIndex(len(X), max, 0)
for key in S:
    li = A[key]
    for x, flag in li:
        if flag == 0:
            st.update(zip_x[x], 1)
        else:
            st.update(zip_x[x], 0)
    if key in Dset:
        mx, idx = st.query(0, len(X))
        B[key] = unzip_x[idx] if mx == 1 else -1
[print(B[x]) for x in D]

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))

#################

from operator import itemgetter
from bisect import bisect_left

class LazySegmentTree:
    def __init__(self,N,default):
        #演算の定義
        self.op = min
        #初期化の値
        self.default = default
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.default]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)

    #伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self,l,r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    #1-indexedで単調増加のインデックスリストを渡す
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.tree[2*i-1] = self.tree[2*i] = self.tree[2*i] = v
            self.lazy[i-1] = None

    #区間[l,r)の値をxに更新
    def update(self,l,r,x):
        if l < r:
            *ids, = self.gindex(l, r)
            self.propagates(*ids)

            L = l + self.N0; R = r + self.N0
            while L < R:
                if R & 1:
                    R -= 1
                    self.lazy[R-1] = self.tree[R-1] = x
                if L & 1:
                    self.lazy[L-1] = self.tree[L-1] = x
                    L += 1
                L >>= 1; R >>= 1

            for i in ids:
                self.tree[i-1] = self.op(self.tree[2*i-1], self.tree[2*i])

    #区間[l,r)へのクエリ
    def query(self,l,r):
        self.propagates(*self.gindex(l, r))
        L = l + self.N0; R = r + self.N0
        s = self.default
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s,self.tree[R-1])
            if L & 1:
                s = self.op(s,self.tree[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    #k番目の値を取得
    def get(self,k):
        return self.tree[k+self.N0-1]

N,Q = II()
S,T,X = Line(N,3)
D = Line(Q,1)

a = []
for i in range(N):
    a.append([X[i], S[i]-X[i]-0.5, T[i]-X[i]-0.5])
a.sort(key=itemgetter(0),reverse=True)

seg = LazySegmentTree(Q,-1)
for i in range(N):
    l = bisect_left(D,a[i][1]) + 1
    r = bisect_left(D,a[i][2]) + 1
    seg.update(l,r,a[i][0])

for i in range(Q):
    print(seg.get(i+1))

Submission status: Wrong Answer

Solution code:
#解説解法
#setは挿入・削除・最小値がO(logn)
#イベントソート
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.sort()
'''
for x in event:
  print(x)
'''
d = []
for _ in range(q):
  d.append(int(input()))
here = 0
now = set()
for qi in range(q):
  if here == 2 * n:
    print(-1)
    continue
  while event[here][0] <= d[qi]:
    if event[here][1] == 1:
      now.add(event[here][2])
    else:
      now.remove(event[here][2])
    here += 1
    if here == 2 * n:
      print(-1)
      break
  else:
    try:
      print(min(now))
    except:
      print(-1)
    #print(now)
    continue
  break

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
xList = []
constStart = []
constStop = []

for i in range(N):
    Si, Ti, Xi = map(int, input().split())
    xList.append(Xi)
    constStart.append(Si-Xi)
    constStop.append(Ti-Xi-1)

dList = []
for i in range(Q):
    dList.append(int(input()))

for i, e in enumerate(dList):
    isConst = False
    minXConst = -1
    for j in range(N):
        if constStart[j] <= e and e <= constStop[j]:
            if xList[j] < minXConst:
                minXConst = xList[j]
    print(minXConst)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
xList = []
constStart = []
constStop = []

for i in range(N):
    Si, Ti, Xi = map(int, input().split())
    xList.append(Xi)
    constStart.append(Si-Xi)
    constStop.append(Ti-Xi-1)

dList = []
for i in range(Q):
    dList.append(int(input()))

for i, e in enumerate(dList): 
    isConst = False
    for j in range(N):
        if constStart[j] <= e and e <= constStop[j]:
            print(xList[j])
            isConst = True
            break
    if not isConst:
        print(-1)

Submission status: Wrong Answer

Solution code:
import bisect


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

    xst = sorted((x, s, t) for s, t, x in stx)
    print(xst)
    D1 = sorted((d, i) for i, d in enumerate(D))
    print(D1)
    ret = [-1] * Q
    for x, s, t in reversed(xst):
        left = bisect.bisect_left(D1, (s - x, -1))
        right = bisect.bisect_left(D1, (t - x, -1))
        for _, i in D1[left:right]:
            ret[i] = x
    print('\n'.join(map(str, ret)))


main()

Submission status: Wrong Answer

Solution code:
#48 ABC128E
#イベントソート
n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]

stx.sort()

ans=[-1 for _ in range(q)]
skip=[-1 for _ in range(q)]

from bisect import bisect_left

for s,t,x in stx:
	left=bisect_left(d,s-x)
	right=bisect_left(d,t-x)
	while left<right:
		if skip[left]==-1:
			ans[left]=x
			skip[left]=right
			left+=1
		else:
			left=skip[left]
for i in range(q):
	print(str(ans[i]))

Submission status: Wrong Answer

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

stx.sort()

ans=[-1 for _ in range(q)]
skip=[-1 for _ in range(q)]

from bisect import bisect_left

for s,t,x in stx:
	left=bisect_left(d,s-x)
	right=bisect_left(d,t-x)
	while left<right:
		if skip[left]==-1:
			ans[left]=x
			skip[left]=right
			left+=1
		else:
			left=skip[left]
	for i in range(q):
		print(str(ans[i]))

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
dct = {}
for i in range(n):
  a,b,c = map(int, input().split())
  dct[(a-0.5,b-0.5)] = c
arr2 = []
for i in range(q):
  arr2.append(int(input()))
max_point = max(dct.values())
all_stopping_points = dct.values()
for time in arr2:
  point = 0
  while True:
    time += 1
    point += 1
    if point in all_stopping_points:
      stop_time_x, stop_time_y = [k for k,v in dct.items() if v == point][0]
      if stop_time_x < time < stop_time_y:
        print(point)
        break
    if point > max_point:
      print(-1)
      break

Submission status: Wrong Answer

Solution code:
# coding: utf-8
class LazySegmentTree:
	INF = 2**31-1
	
	def __init__(self, v):
		sz = len(v)
		self.n = 1
		while (self.n < sz): self.n *= 2
		self.node = [LazySegmentTree.INF] * (2*self.n-1)
		self.lazy = [LazySegmentTree.INF] * (2*self.n-1)
		self.lazyFlag = [False] * (2*self.n-1)
		
		for i in range(sz):
			self.node[self.n-1+i] = v[i]
		for i in reversed(range(self.n-2,0)):
			self.node[i] = min( self.node[2*i+1], self.node[2*i+2])


	# k番目のノードについて遅延評価を行う
	# k:注目するノード番号
	# l:注目するノードの担当範囲の左  r:注目するノードの担当範囲の右
	def lazyEvaluate( self, k, l, r):
		if self.lazyFlag[k]:
			self.node[k] = self.lazy[k]
			if ( r-l > 1):
				self.lazy[2*k+1] = self.lazy[2*k+2] = self.lazy[k]
				self.lazyFlag[2*k+1] = self.lazyFlag[2*k+2] = True
			self.lazyFlag[k] = False
	
	# 区間更新[a,b)をxに更新
	def update( self, a, b, x, k=0, l=0, r=-1):
		if (r < 0): r = self.n
		self.lazyEvaluate(k, l, r)
		# 範囲外なら何もしない
		if (b <= l or r <= a): return
		# 完全に被覆しているならば、遅延配列に値を入れた後に評価
		if (a <= l and r <= b):
			self.lazy[k] = x
			self.lazyFlag[k] = True
			self.lazyEvaluate( k, l, r)
		# 子ノードの値を再帰的に計算して計算済みの値をもらってくる
		else:
			self.update( a, b, x, 2*k+1, l, int((l+r)/2))
			self.update( a, b, x, 2*k+2, int((l+r)/2), r)
			self.node[k] = min( self.node[2*k+1], self.node[2*k+2])
	
	def find( self, a, b, k=0, l=0, r=-1):
		if (r < 0): r = self.n
		self.lazyEvaluate( k, l, r)
		# 1.要求区間と対象区間が交わらない場合
		if (b <= l or r <= a): return LazySegmentTree.INF
		# 2.要求区間が対象区間を完全に被覆している場合
		if (a <= l and r <= b): return self.node[k]
		# 3.要求区間が対象区間の一部を被覆している場合
		L = self.find( a, b, 2*k+1, l, int((l+r)/2))
		R = self.find( a, b, 2*k+2, int((l+r)/2), r)
		return min(L, R)


##-------------------------------------------------
## 座標圧縮
##-------------------------------------------------
#def compress(a):
#	a = list(set(a))
#	a.sort()
#	zip = {}
#	unzip = {}
#	for i in range(len(a)):
#		zip[a[i]] = i
#		unzip[i] = a[i]
#	return zip, unzip


from operator import itemgetter

if __name__ == '__main__':
	N, Q = map(int, input().split())
	roadwork = []
	for i in range(N):
		s, t, x = map(int, input().split())
		roadwork.append([s-x, t-x, x])
	roadwork.sort(key=itemgetter(0,1))
	Ds = [int(input()) for i in range(Q)]
	
	A = [ a for a,b,x in roadwork ] + [ b for a,b,x in roadwork ] + Ds
	A = list(set(A))
	A.sort()

	# 座標圧縮
	unzip = {}
	for i in range(len(A)):
		unzip[A[i]] = i

	lst = LazySegmentTree([-1 for _ in range(len(A))])
	for a, b, x in roadwork:
		lst.update(unzip[a], unzip[b], x)
	for i in range(len(Ds)):
		a = unzip[Ds[i]]
		print(lst.find(a, a+1))

#	#--------------------------------------------
#	print("-------------------------------------")
#	[ lst.find(i, i+1) for i in range(len(A))]
#	rn = [0,2,6,14,30,62]
#	for i in range(len(lst.node)):
#		if i in rn:
#			print(lst.node[i])
#		else:
#			print(lst.node[i],end="\t")
#	#--------------------------------------------

Submission status: Wrong Answer

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
skip = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    
    i = left
    while i < right:
        if skip[i] == -1:
            ans[i] = x
            skip[i] = right
        else:
            i = skip[i]

    
#print(walkers)
for a in ans:
    print(a)

Submission status: Wrong Answer

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
skip = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    #print(left, right)
    for i in range(max(skip[left], left), right):
        #print(i)
        ans[i] = x
        skip[i] = right-1
    
#print(walkers)
for a in ans:
    print(a)

Submission status: Wrong Answer

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
    
    
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks)
#print(roadworks)

# Dは入力時点でソート済み
walkers = D[:]
ans = [-1] * len(walkers)
skip = [-1] * len(walkers)
import bisect
for x, s, t in roadworks:
    left = bisect.bisect_left(walkers, s - x)
    right = bisect.bisect_left(walkers, t - x)
    #print(left, right)
    for i in range(max(skip[left], left), right):
        #print(i)
        ans[i] = x
        skip[i] = right
    
#print(walkers)
for a in ans:
    print(a)

Submission status: Wrong Answer

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

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

D = [None] * Q
for i in range(Q):
    D[i] = int(input())
# X S T
roadworks = [(x, s, t) for x, s, t in zip(X, S, T)]
roadworks = sorted(roadworks, reverse=True)
#print(roadworks)

from collections import defaultdict
stops = [-1]*(10**5)
be = []
for x, s, t in roadworks:
    be.append((max(0,s-x), 1, x))
    be.append((max(0,t-x), -1, x))
be = sorted(be, key=lambda x: (x[0], x[2]))
#print(be)

D_i = 0
import heapq
current_works = []
from collections import defaultdict
del_dict = defaultdict(int)
for w in be:
    if w[0] <= D[D_i]:
        pass
    else:
        while True:
            if current_works:
                min_v = current_works[0]
                if del_dict[min_v] > 0:
                    del_dict[min_v] -= 1
                    heapq.heappop(current_works)
                else:
                    print(min_v)
                    D_i += 1
                    break
            else:
                print(-1)
                D_i += 1
                break
            
    
    if w[1] == 1:
        heapq.heappush(current_works, w[2])
    else:
        del_dict[w[2]] += 1
for i in D[D_i:]:
    print(-1)