Problem:


Score : 500 points

Problem Statement

There is an infinitely long street that runs west to east, which we consider as a number line.

There are N roadworks scheduled on this street.
The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.

Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the Q people will walk.

Constraints

All values in input are integers.

1 \leq N, Q \leq 2 \times 10^5

0 \leq S_i < T_i \leq 10^9

1 \leq X_i \leq 10^9

0 \leq D_1 < D_2 < ... < D_Q \leq 10^9

If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Input

Input is given from Standard Input in the following format:

N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q

Output

Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

Sample Input 1

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

Sample Output 1

2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.

The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.

The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.



Sample input:
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8


Sample output:
2
2
10
-1
13
-1

Submission status: Time Limit Exceeded

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

n,Q=map(int,input().split())
xs = []
ts = set()
qs = []
for _ in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x), (t-x-0.5,False,x)]
    ts.add(x)
for _ in range(Q):
    xs.append((int(input()), 2, 0))
xs.sort(key=lambda x:x[0])

mx,XN = 10**9,len(ts)
x2i = {x:i for i,x in enumerate(ts)}
st = SegTree([mx]*XN, XN, mx, min)
for t,r,x in xs:
    if r == 2:
        c = st.query(0,XN)
        print(c if c!= mx else -1)
    else:
        st.update(x2i[x], x if r else mx)

Submission status: Time Limit Exceeded

Solution code:
import sys
class SegTree:
    def __init__(self, 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 
        
    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):
        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

input = sys.stdin.readline

n,Q=map(int,input().split())
xs = []
qs = []
for i in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
for _ in range(Q):
    xs.append((int(input()), 2, 0,0))
xs.sort(key=lambda x:x[0])

mx,XN = 10**9,n
st = SegTree(XN, mx, min)
for t,r,x,i in xs:
    if r == 2:
        c = st.query(0,XN)
        print(c if c!= mx else -1)
    else:
        st.update(i, x if r else mx)

Submission status: Time Limit Exceeded

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

n,Q=map(int,input().split())
xs = []
ts = set()
qs = []
for _ in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x), (t-x-0.5,False,x)]
    ts.add(x)
for _ in range(Q):
    xs.append((int(input()), 2, 0))
xs.sort(key=lambda x:x[0])
xs += [(10**9,True,x)]

mx = max(ts) + 1
tmp = list(ts)
x2i = dict()
for i, x in enumerate(ts):
    x2i[x] = i



XN = len(ts)
st = SegTree([mx]*XN, XN, mx, min)
for t,r,x in xs:
    if r == 2:
        c = st.query(0,XN)
        print(c if c!= mx else -1)
    else:
        st.update(x2i[x], x if r else mx)

Submission status: Time Limit Exceeded

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

n,Q=map(int,input().split())
xs = []
ts = set()
for _ in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x), (t-x-0.5,False,x)]
    ts.add(x)
xs.sort(key=lambda x:x[0])
xs += [(10**9,True,x)]

mx = max(ts) + 1
tmp = list(ts)
x2i = dict()
for i, x in enumerate(ts):
    x2i[x] = i



XN = len(ts)
st = SegTree([mx]*XN, XN, mx, min)
q = int(input())
for t,r,x in xs:
    if q < t:
        c = st.query(0,XN)
        while True:
            if q >= t:
                break
            print(c if c!= mx else -1)
            Q-=1
            if not Q:
                sys.exit()
            q = int(input())
    st.update(x2i[x], x if r else mx)

Submission status: Time Limit Exceeded

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

n,Q=map(int,input().split())
xs = []
for _ in range(n):
    s,t,x=map(int,input().split())
    xs += [(s-x-0.4,True,x), (t-x-0.5,False,x)]
xs.sort(key=lambda x:x[0])
xs += [(10**9,True,x)]

h=set()
q = int(input())
for t,r,x in xs:
    if q < t:
        if h:
            c = min(h)
        else:
            c = -1
        while True:
            if q >= t:
                break
            print(c)
            Q-=1
            if not Q:
                sys.exit()
            q = int(input())
    if r:
        h.add(x)
    else:
        h.remove(x)

Submission status: Time Limit Exceeded

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 = min(h)
        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: Time Limit Exceeded

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 += [(s,1,x), (t,0,x)]
    tmp.add(x)
for _ in range(Q):
    qs.append(int(input()))

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

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

Submission status: Time Limit Exceeded

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()
mx = max(tmp) + 1
tmp = list(tmp)
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

qi = 0
q = qs[qi]
XN = len(tmp)
st = SegTree([mx]*XN, XN, mx, min)
for t,r,x in xs:
    if q < t:
        c = st.query(0,XN)
        while True:
            if q < t:
                if c != mx:
                    print(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
    if r:
        st.update(x2i[x], x)
    else:
        st.update(x2i[x], mx)
print("-1\n"*Q)

Submission status: Time Limit Exceeded

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
    if r:
        st.update(x2i[x], x2i[x])
    else:
        st.update(x2i[x], XN)
print("-1\n"*Q)

Submission status: Time Limit Exceeded

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 = 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: Time Limit Exceeded

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 = [],[],[]
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.append(x)
xs.sort()
tmp = list(set(tmp))
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

q = int(input())
rs = set()
st = SegTree([len(tmp)]*len(tmp), len(tmp), len(tmp), min)
for t,r,x in xs:
    while True:
        if q < t:
            c = st.query(0,len(tmp))
            if c != len(tmp):
                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], len(tmp))
print("-1\n"*Q)

Submission status: Time Limit Exceeded

Solution code:
# 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 = [],[],[]
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.append(x)
xs.sort()
tmp = list(set(tmp))
tmp.sort()
x2i = dict()
for i, x in enumerate(tmp):
    x2i[x] = i

q = int(input())
rs = set()
st = SegTree([len(tmp)]*len(tmp), len(tmp), len(tmp), min)
for t,r,x in xs:
    while True:
        if q < t:
            c = st.query(0,len(tmp))
            if c != len(tmp):
                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], len(tmp))
print("-1\n"*Q)

Submission status: Time Limit Exceeded

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())
rs = set()
for t,r,x in xs:
    while True:
        if q < t:
            if rs:
                print(min(rs))
            else:
                print(-1)
            Q-=1
            if Q == 0:
                break
            q = int(input())
        else:
            break
#    print(t,r,x)
    if Q==0:
        break
    if not r:
        rs.remove(x)
    else:
        rs.add(x)
print("-1\n"*Q)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def update(x, v):
  k = _N + x
  ST[k] = v
  while k > 1:
    p = k // 2
    ST[p] = min(ST[2 * p], ST[2 * p + 1])
    k = p
def getMin(i):
  if _N <= i:
    return ST[i]
  if ST[i] == C:
    return C
  return min(getMin(2 * i), getMin(2 * i + 1))
N, Q = map(int, input().split())
C = 10 ** 9 + 1
_N = 1
while _N <= N:
  _N *= 2
ST = [C] * (2 * _N)
HQ = []
for i in range(N):
  S, T, X = map(int, input().split())
  heapq.heappush(HQ, [S - X - 0.5, i, X])
  heapq.heappush(HQ, [T - X - 0.5, i, C])
for i in range(Q):
  D = int(input())
  heapq.heappush(HQ, [D, i])
A = ['' for _ in range(Q)]
while HQ:
  e = heapq.heappop(HQ)
  if len(e) > 2:
    update(e[1], e[2])
  else:
    l = getMin(1)
    A[e[1]] = str(l if l < C else -1)
print('\n'.join(A))

Submission status: Time Limit Exceeded

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

import sys
from heapq import heappush, heappop

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

N, Q = MAP()
# 3種類の状態変化をイベントとして一括管理する
# 0: 工事終了, 1: 工事開始, 2: 人の出発
events = []
for i in range(N):
    s, t, x = MAP()
    # (開始座標に合わせた状態の工事開始時間, フラグ, 実際の座標)
    events.append((s-x, 1, x))
    # (開始座標に合わせた状態の工事終了時間, フラグ, 実際の座標)
    events.append((t-x, 0, x))
for i in range(Q):
    d = INT()
    # (人の出発時間, フラグ, index)
    events.append((d, 2, i))
# 時系列に沿ってソート、フラグも同時刻な時先に処理して欲しいものから番号を振ってある
events.sort()

# setとheapqを合わせて、時刻に合わせた処理と最小値取得を行う
S = set()
hp = []
ans = [0] * Q
for t, flag, x in events:
    # 工事終了
    if flag == 0:
        S.remove(x)
    # 工事開始
    elif flag == 1:
        S.add(x)
        heappush(hp, x)
    # 人の移動
    elif flag == 2:
        # heapqの先頭要素ついて、setと状態を合わせる
        while len(hp) and hp[0] not in S:
            heappop(hp)
        if len(hp):
            ans[x] = hp[0]
        else:
            ans[x] = -1
[print(a) for a in ans]

Submission status: Time Limit Exceeded

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

import sys
from collections import Counter, 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

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

Dset = set(D)
S = sorted(X|Dset)
B = {}
C = Counter()
for key in S:
    if key in A:
        for x, flag in A[key]:
            if flag == 0:
                C[x] += 1
            else:
                C[x] -= 1
            if C[x] == 0:
                del C[x]
    if key in Dset:
        mn = min(C) if len(C) else -1
        B[key] = mn
[print(B[x]) for x in D]

Submission status: Time Limit Exceeded

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

import sys
from collections import Counter, 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

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

Dset = set(D)
S = sorted(X|Dset)
B = {}
C = Counter()
for key in S:
    li = A[key]
    for x, flag in li:
        if flag == 0:
            C[x] += 1
        else:
            C[x] -= 1
        if C[x] == 0:
            del C[x]
    if key in Dset:
        mn = min(C) if len(C) else -1
        B[key] = mn
[print(B[x]) for x in D]

Submission status: Time Limit Exceeded

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

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """
    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

class BIT:

    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

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]

def calc(m):
    cnt = bit.sum(m)
    return cnt > 0

Dset = set(D)
S = sorted(ST|Dset)
B = {}
bit = BIT(len(X))
for key in S:
    li = A[key]
    for x, flag in li:
        if flag == 0:
            bit.add(zip_x[x], 1)
        else:
            bit.add(zip_x[x], -1)
    if key in Dset:
        # BIT二分探索
        mn = bisearch_min(-1, len(X), calc)
        B[key] = unzip_x[mn] if mn != len(X) else -1
[print(B[x]) for x in D]