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 numpy as np
# 二部探索で決めていく。dpですでに見られたかどうかは把握
from bisect import bisect_left
n,q  = map(int, input().split())
events = []
"""
工事 start   0 eve追加
di start     2
工事 finish  1 eve削除
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
for i in range(n):
    s,t,x = map(int, input().split())
    events.append((s-x,1,x))
    events.append((t-x,-1,x))
    
for i in range(q):
    d = int(input())
    events.append((d,2,i))
ans = [-1] * q
events.sort()
works = set()
for t, e, x in events:
    if e == 1:
        works.add(x)
    elif e == -1:
        works.remove(x)
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            ans[x] = min(works)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
  elif f==-1:
    stop_set.remove(x)
  else:
    if len(stop_set)>0:
      answer_dic[t]=min(stop_set)
#print(answer_dic)

for d in dlist:
  if d in answer_dic:
    print(answer_dic[d])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def main():
    class BIT:
        def __init__(self, n):
            self.num = n
            self.dat = [0] * (self.num + 1)
            self.depth = n.bit_length()
            self.total = 0

        def add(self, i, x):
            i += 1
            self.total += x
            while i <= self.num:
                self.dat[i] += x
                i += i & -i

        def sum(self, i):
            i += 1
            s = 0
            while i > 0:
                s += self.dat[i]
                i -= i & -i
            return s

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.num and sum_ + self.dat[k] < x:
                    sum_ += self.dat[k]
                    pos += 1 << i
            return pos

    n, q = LI()
    L = []
    co_set = set()
    for i in range(n):
        s, t, x = LI()
        L += [(s - x, 0, x)]
        L += [(t - x, 1, x)]
        co_set.add(x)
        co_set.add(x)

    for j in range(q):
        d = I()
        L += [(d, 2, 0)]

    idx_to_co = sorted(list(co_set))
    L.sort()
    D = {e:j for j, e in enumerate(sorted(co_set))}
    bit = BIT(len(D))
    for t, z, block in L:
        if z == 2:
            if bit.total:
                print(idx_to_co[bit.lower_bound(1)])
            else:
                print(-1)
        elif z == 0:
            bit.add(D[block], 1)
        else:
            bit.add(D[block], -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def main():
    class BIT:
        def __init__(self, n):
            self.num = n
            self.dat = [0] * (self.num + 1)
            self.depth = n.bit_length()
            self.total = 0

        def add(self, i, x):
            i += 1
            self.total += x
            while i <= self.num:
                self.dat[i] += x
                i += i & -i

        def sum(self, i):
            i += 1
            s = 0
            while i > 0:
                s += self.dat[i]
                i -= i & -i
            return s

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.num and sum_ + self.dat[k] < x:
                    sum_ += self.dat[k]
                    pos += 1 << i
            return pos

    n, q = LI()
    L = []
    co_set = set()
    for i in range(n):
        s, t, x = LI()
        L += [(s - x, 0, x)]
        L += [(t - x, 1, x)]
        co_set.add(x)
        co_set.add(x)

    for j in range(q):
        d = I()
        L += [(d, 2, 0)]

    idx_to_co = sorted(co_set)
    L.sort()
    D = {e:j for j, e in enumerate(sorted(co_set))}
    bit = BIT(len(D))
    q = []
    for t, z, block in L:
        if z == 2:
            if bit.total:
                print(idx_to_co[bit.lower_bound(1)])
            else:
                print(-1)
        elif z == 0:
            bit.add(D[block], 1)
        else:
            bit.add(D[block], -1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



class BIT:
    def __init__(self, n):
        self.num = n
        self.dat = [0] * (self.num + 1)
        self.depth = n.bit_length()
        self.total = 0

    def add(self, i, x):
        i += 1
        self.total += x
        while i <= self.num:
            self.dat[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.dat[i]
            i -= i & -i
        return s

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.num and sum_ + self.dat[k] < x:
                sum_ += self.dat[k]
                pos += 1 << i
        return pos

n, q = LI()
L = []
co_set = set()
for i in range(n):
    s, t, x = LI()
    L += [(s - x, 0, x)]
    L += [(t - x, 1, x)]
    co_set.add(x)
    co_set.add(x)

for j in range(q):
    d = I()
    L += [(d, 2, 0)]

idx_to_co = sorted(co_set)
L.sort()
D = {e:j for j, e in enumerate(sorted(co_set))}
bit = BIT(len(D))
q = []
for t, z, block in L:
    if z == 2:
        if bit.total:
            print(idx_to_co[bit.lower_bound(1)])
        else:
            print(-1)
    elif z == 0:
        bit.add(D[block], 1)
    else:
        bit.add(D[block], -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, k):
        if k > self.total or k < 0:
            return -1
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index

n, q = LI()
L = []
co_set = set()
for i in range(n):
    s, t, x = LI()
    L += [(s - x, 0, x)]
    L += [(t - x, 1, x)]
    co_set.add(x)
    co_set.add(x)

for j in range(q):
    d = I()
    L += [(d, 2, 0)]

idx_to_co = sorted(co_set)
L.sort()
D = {e:j for j, e in enumerate(sorted(co_set))}
bit = BIT(len(D))
q = []
for t, z, block in L:
    if z == 2:
        if bit.total:
            print(idx_to_co[bit.search(1)])
        else:
            print(-1)
    elif z == 0:
        bit.add(D[block], 1)
    else:
        bit.add(D[block], -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
STX = []
D = []
D2 = []
ans = [0]*Q
timer = 0
m = 0

for _ in range(N):
    stx = list(map(int, input().split()))
    STX.append(stx)
    if stx[2] > m:
        m = stx[2]

for _ in range(Q):
    ds = int(input())
    D.append(-ds)
    D2.append(-ds)

while True:
    for d in D:
        if d > 0:
            for s in STX:
                if d == s[2] and timer >= s[0] and timer < s[1]:
                    ans[D2.index(d-timer)] = D.pop(D.index(d))
                    break
                
    if D == []:
        break

    elif min(D) >= m:
        for a in ans:
            if a == 0:
                print(-1)
            else:
                print(a)
        break

    D = list(map(lambda x: x+1, D))
    timer += 1

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline()
from bisect import bisect_left, bisect_right

class LazySegmentTree:
    INF = float("inf")

    def __init__(self, n):
        self.n = 1 << (n-1).bit_length()
        self.data = [self.INF] * (self.n*2)
        self.lazy = [None] * (self.n*2)
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = min(self.data[i*2], self.data[i*2+1])
        
    def query(self, l, r):
        if not l < r: return self.INF
        self.__propagate(self.__getidx(l, r))

        l += self.n; r += self.n 
        res = self.INF
        while l < r:
            if l & 1:
                res = min(res, self.data[l])
                l += 1
            if r & 1:
                res = min(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def update(self, l, r, x):
        if not l < r: return
        idx = self.__getidx(l, r)
        self.__propagate(idx)

        l += self.n; r += self.n 
        while l < r:
            if l & 1:
                self.data[l], self.lazy[l] = x, x
                l += 1
            if r & 1:
                self.data[r-1], self.lazy[r-1] = x, x
            l >>= 1; r >>= 1
    
        for i in idx:
            self.data[i] = min(self.data[i*2], self.data[i*2+1])

    def __getidx(self, l, r):
        l += self.n; r += self.n 
        lm = l // ((l & -l) << 1)
        rm = r // ((r & -r) << 1)
        res = []
        while l < r:
            if l <= lm: res.append(l)
            if r <= rm: res.append(r)
            l >>= 1; r >>= 1
        while l:
            res.append(l)
            l >>= 1
        return res
    
    def __propagate(self, idx):
        for i in reversed(idx):
            val = self.lazy[i]
            if val is None: continue
            self.lazy[i*2] = val; self.lazy[i*2+1] = val
            self.data[i*2] = val; self.data[i*2+1] = val
            self.lazy[i] = None

n, q = map(int, input().split())
query = [None] * n
for i in range(n):
    s, t, x = map(int, input().split())
    query[i] = s-x, t-x, x
d = [int(input()) for _ in range(q)]
lst = LazySegmentTree(q)

query.sort(key=lambda x: x[2], reverse=True)

for l, r, x in query:
    lst.update(bisect_left(d, l), bisect_left(d, r), x)

for i in range(q):
    ans = lst.query(i, i+1)
    print(-1 if ans == float("inf") else ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

class LazySegmentTree:
    INF = float("inf")

    def __init__(self, n):
        self.n = 1 << (n-1).bit_length()
        self.data = [self.INF] * (self.n*2)
        self.lazy = [None] * (self.n*2)
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = min(self.data[i*2], self.data[i*2+1])
        
    def query(self, l, r):
        if not l < r: return self.INF
        self.__propagate(self.__getidx(l, r))

        l += self.n; r += self.n 
        res = self.INF
        while l < r:
            if l & 1:
                res = min(res, self.data[l])
                l += 1
            if r & 1:
                res = min(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def update(self, l, r, x):
        if not l < r: return
        idx = self.__getidx(l, r)
        self.__propagate(idx)

        l += self.n; r += self.n 
        while l < r:
            if l & 1:
                self.data[l], self.lazy[l] = x, x
                l += 1
            if r & 1:
                self.data[r-1], self.lazy[r-1] = x, x
            l >>= 1; r >>= 1
    
        for i in idx:
            self.data[i] = min(self.data[i*2], self.data[i*2+1])

    def __getidx(self, l, r):
        l += self.n; r += self.n 
        lm = l // ((l & -l) << 1)
        rm = r // ((r & -r) << 1)
        res = []
        while l < r:
            if l <= lm: res.append(l)
            if r <= rm: res.append(r)
            l >>= 1; r >>= 1
        while l:
            res.append(l)
            l >>= 1
        return res
    
    def __propagate(self, idx):
        for i in reversed(idx):
            val = self.lazy[i]
            if val is None: continue
            self.lazy[i*2] = val; self.lazy[i*2+1] = val
            self.data[i*2] = val; self.data[i*2+1] = val
            self.lazy[i] = None

n, q = map(int, input().split())
query = [None] * n
for i in range(n):
    s, t, x = map(int, input().split())
    query[i] = s-x, t-x, x
d = [int(input()) for _ in range(q)]
lst = LazySegmentTree(q)

query.sort(key=lambda x: x[2], reverse=True)

for l, r, x in query:
    lst.update(bisect_left(d, l), bisect_left(d, r), x)

for i in range(q):
    ans = lst.query(i, i+1)
    print(-1 if ans == float("inf") else ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    unique_X=sorted(list(set(X)))
    d={unique_X[i]:i for i,x in enumerate(unique_X)}
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,d[X[i]]))
        l.append((T[i]-X[i],-1,d[X[i]]))
    for i in range(Q):
        l.append((int(input()),2,0))
    l.sort()
    b=BIT(len(unique_X))
    for t,q,x in l:
        if q==-1:
            b.add(x,-1)
        elif q==1:
            b.add(x,1)
        else:
            res,_=b.lower_bound(1)
            print(unique_X[res] if res<len(unique_X) else -1)
        


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    unique_X=sorted(list(set(X)))
    d={unique_X[i]:i for i,x in enumerate(unique_X)}
    h=[]
    for i in range(N):
        heappush(h,(S[i]-X[i],1,d[X[i]]))
        heappush(h,(T[i]-X[i],-1,d[X[i]]))
    for _ in range(Q):
        heappush(h,(int(input()),2,0))
    b=BIT(len(unique_X))
    c=0
    for _ in range(N*2+Q):
        t,q,x=heappop(h)
        if q==-1:
            c-=1
            b.add(x,-1)
        elif q==1:
            c+=1
            b.add(x,1)
        else:
            res,_=b.lower_bound(1)
            print(unique_X[res] if res<len(unique_X) else -1)
        


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    unique_X=sorted(list(set(X)))
    d={unique_X[i]:i for i,x in enumerate(unique_X)}
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,d[X[i]]))
        l.append((T[i]-X[i],-1,d[X[i]]))
    l+=[(int(input()),2,0) for _ in range(Q)]
    l.sort()
    b=BIT(len(unique_X))
    c=0
    for t,q,x in l:
        if q==-1:
            c-=1
            b.add(x,-1)
        elif q==1:
            c+=1
            b.add(x,1)
        else:
            res,_=b.lower_bound(1)
            print(unique_X[res] if res<len(unique_X) else -1)
        


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, collections, heapq
def input(): return sys.stdin.readline().strip()

def main():
    """
    スマートそうな別解を見つけたのでこちらも解読してみる
    https://atcoder.jp/contests/abc128/submissions/5654668
    """
    N, Q = map(int, input().split())
    add = []
    delete = []
    for i in range(N):
        S, T, X = map(int, input().split())
        add.append((S - X, X))
        delete.append((T - X, X))
    heapq.heapify(add)
    heapq.heapify(delete)

    """
    以下自力で思いつける気がしないぞ。工事一つずつ見て行って引っかかりうるものを検査している。
    d1,...,dQは昇順に並んでいるので、
        前の人で工事に引っかかりうる　→　次の人も工事に引っかかりうる
        前の人が実は工事に引っかからない　→　次の人も実は工事に引っかからない
    により、引っかかりうる工事の集合はQ回のループで使いまわせる。
    """

    active = []
    to_delete = collections.defaultdict(int)
    for _ in range(Q):
        x = int(input())
        while add and add[0][0] <= x: # xが工事に引っかかる可能性があれば、工事座標をactiveに追加
            S, X = heapq.heappop(add)
            heapq.heappush(active, X)

        while delete and delete[0][0] <= x: # xが工事終了後に工事現場を通過する場合、それをto_deleteに記録
            T, X = heapq.heappop(delete)
            to_delete[X] += 1

        while active and to_delete[active[0]] > 0: # 工事に引っかかる可能性のあるもので、実は工事に引っかからないものは除外
            to_delete[active[0]] -= 1
            heapq.heappop(active)

        print(active[0] if active else -1) # 一巡してもactiveは空になっていないことに注意


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
STX=[]
for _ in range(N):
  STX.append(list(map(int,input().split())))
D=[]
for _ in range(Q):
  D.append(int(input()))
STX.sort(key=lambda x:x[2])
for d in D:
  ans=-1
  for s,t,x in STX:
    if s-0.5<d+x<t-0.5:
      ans=x
      break
  print(ans)

Submission status: Time Limit Exceeded

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

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
min_set=10**9
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
    if x<min_set:
      min_set=x
  elif f==-1:
    stop_set.remove(x)
    if x==min_set:
      if len(stop_set)>0:
        min_set=min(stop_set)
      else:
        min_set=10**9
  else:
    if len(stop_set)>0:
      answer_dic[t]=min_set
    else:
      answer_dic[t]=-1
#print(answer_dic)

for d in dlist:
  print(answer_dic[d])

Submission status: Time Limit Exceeded

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

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
hq=[]
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
    heapq.heappush(hq,x)
  elif f==-1:
    stop_set.remove(x)
  else:
    if len(stop_set)>0:
      while(True):
        if hq[0] in stop_set:
          answer_dic[t]=hq[0]
          break
        else:
          heapq.heappop(hq)
    else:
      answer_dic[t]=-1
      hq=[]
#print(answer_dic)

for d in dlist:
  print(answer_dic[d])

Submission status: Time Limit Exceeded

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

event_list=[]
for i in range(N):
  S,T,X=map(int,input().split())
  event_list.append((S-X-0.5,1,X))
  event_list.append((T-X-0.5,-1,X))
  
dlist=[]
for i in range(Q):
  D=int(input())
  event_list.append((D,0,X))  
  dlist.append(D)
event_list.sort()
#print(event_list)

answer_dic={}
stop_set=set()
hq=[]
for t,f,x in event_list:
  if f==1:
    stop_set.add(x)
    heapq.heappush(hq,x)
  elif f==-1:
    stop_set.remove(x)
  else:
    if len(stop_set)>0:
      while(True):
        if hq[0] in stop_set:
          answer_dic[t]=hq[0]
          break
        else:
          heapq.heappop(hq)
    else:
      answer_dic[t]=-1
#print(answer_dic)

for d in dlist:
  print(answer_dic[d])

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

n, q = [int(x) for x in input().split()]

n *= 2
c_list = [None] * n
for i in range(0, n, 2):
    s, t, x = [int(temp) for temp in input().split()]
    c_list[i] = (s - x, 1, x)
    c_list[i + 1] = (t - x, -1, x)
c_list.sort()

temp_set = set()
temp_list = []

j = 0
for i in range(q):
    d = int(input())
    while j < n and d >= c_list[j][0]:
        if c_list[j][1] == -1:
            temp_set.remove(c_list[j][2])
        elif c_list[j][1] == 1:
            temp_set.add(c_list[j][2])
            heappush(temp_list, c_list[j][2])
        j += 1
    
    while temp_list:
        if temp_list[0] not in temp_set:
            heappop(temp_list)
        else:
            break
    
    p = temp_list[0] if temp_list else -1
    print(p)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, q = [int(x) for x in input().split()]

n *= 2
c_list = [None] * n
for i in range(0, n, 2):
    s, t, x = [int(temp) for temp in input().split()]
    c_list[i] = (s - x, 1, x)
    c_list[i + 1] = (t - x, -1, x)
c_list.sort()

cnt = Counter()
j = 0
for i in range(q):
    d = int(input())
    while j < n and d >= c_list[j][0]:
        cnt[c_list[j][2]] += c_list[j][1]
        j += 1
    
    temp_list = sorted(cnt.elements())
    p = temp_list[0] if len(temp_list) > 0 else -1
    print(p)

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(x) for x in input().split()]

c_list = []
for _ in range(n):
    s, t, x = [int(temp) for temp in input().split()]
    c_list.append((x, s, t))
c_list.sort()

for _ in range(q):
    d = int(input())
    p = -1
    for x, s, t in c_list:
        if s<= d + x < t:
            p = x
            break
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

def main():
    n,q = map(int, input().split())
    tl = []
    ins = list()
    dlt = list()
    for _ in range(n):
        s,t,x = map(int, input().split())
        tl.append((s-x,1,x))
        tl.append((t-x,0,x))
    for _ in range(q):
        t = int(input())
        tl.append((t,2))
    tl.sort()

    for x in tl:
        if x[1] == 1:
            hq.heappush(ins, x[2])
        elif x[1] == 0:
            hq.heappush(dlt, x[2])
            while dlt and ins[0] == dlt[0]:
                hq.heappop(ins)
                hq.heappop(dlt)
        else:
            print(-1 if not ins else ins[0])
    
if __name__ == "__main__":
    main()