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
from operator import itemgetter


scan = sys.stdin.readline


def main():
    n, q = map(int, scan().rstrip().split())
    schedules = [tuple(map(int, scan().rstrip().split())) for _ in range(n)]
    d = [int(scan().rstrip()) for _ in range(q)]

    pos = [[0, False] for _ in range(q)]

    schedules.sort(key=itemgetter(0))
    construction = []

    # caution
    for time in range(schedules[n - 1][1] + 1):
        construction = [scd[2] for scd in schedules if scd[0] <= time < scd[1]]

        for person in range(q):
            if d[person] < time and not pos[person][1]:
                pos[person][0] += 1
                if construction.count(pos[person][0]) > 0:
                    pos[person][1] = True

    for position, has_stopped in pos:
        if has_stopped:
            print(position)
        else:
            print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for i in range(N)]
D = [int(input()) for i in range(Q)]

from bisect import *

es = []

for s, t, x in STX:
    t1 = s - .5 - x
    t2 = t - .5 - x
    #print(t1, t2, x)
    es.append((t1, 1, x))
    es.append((t2, 0, x))

for d in D:
    es.append((d, 3, 0))

es.sort()

s = set()

for t, typ, x in es:
    if typ == 3:
        r = -1
        if s:
            r = min(s)
        print(r)
    elif typ == 1:
        s.add(x)
    elif typ == 0:
        s.remove(x)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import heapq

n, q = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(n)]
D = [int(input()) for i in range(q)]

add = [[] for i in range(q + 1)]
remove = [[] for i in range(q + 1)]
last = 0

for i in range(n):
    S[i][0] = max(0, S[i][0] - S[i][2])
    S[i][1] = max(0, S[i][1] - S[i][2])

S.sort(key=lambda s:(s[0], s[2]))

for i in range(n):
    left = bisect_left(D, S[i][0])
    right = bisect_left(D, S[i][1])
    add[left].append(S[i][2])
    remove[right].append(S[i][2])

ans = []
R = []

for i in range(q):
    for a in add[i]:
        heapq.heappush(ans, a)
    for r in remove[i]:
        heapq.heappush(R, r)

    while(ans and R and ans[0] == R[0]):
        heapq.heappop(ans)
        heapq.heappop(R)

    print(ans[0] if ans else -1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import heapq

n, q = [int(i) for i in input().split()]
S = [[int(i) for i in input().split()] for j in range(n)]
D = [int(input()) for i in range(q)]

add = [[] for i in range(q + 1)]
remove = [[] for i in range(q + 1)]
last = 0

for i in range(n):
    S[i][0] = max(0, S[i][0] - S[i][2])
    S[i][1] = max(0, S[i][1] - S[i][2])

S.sort(key=lambda s:(s[0], s[2]))

for i in range(n):
    left = bisect_left(D, S[i][0])
    right = bisect_left(D, S[i][1])
    add[left].append(S[i][2])
    remove[right].append(S[i][2])

ans = []
R = []

for i in range(q):
    for a in add[i]:
        heapq.heappush(ans, a)
    for r in remove[i]:
        heapq.heappush(R, r)

    while(ans and R and ans[0] == R[0]):
        heapq.heappop(ans)
        heapq.heappop(R)

    print(ans[0] if ans else -1)

Submission status: Time Limit Exceeded

Solution code:

N, Q = map(int,input().split())
stx = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

T, u_constr = [], set([])
for i in range(N):
    s, t = stx[i][0] - stx[i][2], stx[i][1] - stx[i][2]
    T.append([stx[i][0] - stx[i][2], 1, stx[i][2]])
    T.append([stx[i][1] - stx[i][2], -1, stx[i][2]])
for q in D:
    T.append([q,2])
T.sort()

T.sort()
for t in T:
    if t[1] == 1:
        u_constr.add(t[2])
    elif t[1] == -1:
        u_constr.remove(t[2])
    else:
        if len(u_constr) > 0:
            print(min(u_constr))
        else:
            print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import bisect
import copy
N, Q = map(int, input().split())
events = []
for i in range(N):
    s,t,x = map(int, input().split())
    events.append([s-x, 1, x])
    events.append([t-x, -1, x])
events.sort()
events=np.array(events)
sets = set()
prev = 0
for _ in range(Q):
    d = int(input())
    index = bisect.bisect_right(events[:,0], d)
    for i in range(prev, index):
        t, pm, x = events[i]
        if pm == 1:
            sets.add(x)
        if pm == -1:
            sets.remove(x)
    prev=copy.copy(index)
    if len(sets)==0:
        print(-1)
    else:
        print(min(sets))

Submission status: Time Limit Exceeded

Solution code:
#event sort
import bisect
N, Q = map(int, input().split())
events = []
for i in range(N):
    s,t,x = map(int, input().split())
    events.append([s-x, 1, x])
    events.append([t-x, -1, x])
events.sort()
sets = set()
for _ in range(Q):
    d = int(input())
    eventime = [event[0] for event in events]
    index = bisect.bisect_right(eventime, d)
    for _ in range(index):
        t, pm, x = events.pop(0)
        if pm == 1:
            sets.add(x)
        if pm == -1:
            sets.remove(x)
    if len(sets)==0:
        print(-1)
    else:
        print(min(sets))

Submission status: Time Limit Exceeded

Solution code:
#event sort
import bisect
N, Q = map(int, input().split())
events = [[0,0,0] for _ in range(2*N)]
for i in range(N):
    s,t,x = map(int, input().split())
    events[2*i]=[s-x, 1, x]
    events[2*i+1]=[t-x, -1, x]
events.sort()
sets = set()
for _ in range(Q):
    d = int(input())
    eventime = [event[0] for event in events]
    index = bisect.bisect_right(eventime, d)
    for _ in range(index):
        t, pm, x = events.pop(0)
        if pm == 1:
            sets.add(x)
        if pm == -1:
            sets.remove(x)
    if len(sets)==0:
        print(-1)
    else:
        print(min(sets))

Submission status: Time Limit Exceeded

Solution code:
#event sort
import bisect
N, Q = map(int, input().split())
consts = [list(map(int, input().split())) for _ in range(N)]
events = [[0,0,0] for _ in range(2*N)]
for i,const in enumerate(consts):
    s,t,x = const
    events[2*i]=[s-x, 1, x]
    events[2*i+1]=[t-x, -1, x]
events.sort()
sets = set()
for _ in range(Q):
    d = int(input())
    eventime = [event[0] for event in events]
    index = bisect.bisect_right(eventime, d)
    for _ in range(index):
        t, pm, x = events.pop(0)
        if pm == 1:
            sets.add(x)
        if pm == -1:
            sets.remove(x)
    if len(sets)==0:
        print(-1)
    else:
        print(min(sets))

Submission status: Time Limit Exceeded

Solution code:
import bisect

#入力処理
n, q = [int(v) for v in input().split()]

#通行止め期間と座標
#座標1移動するのに時間1かかるので、期間から座標を引くとどの期間にスタートすると通行止めにかかるかというデータに変換できる
norm_stxn = []
for i in range(n):
  s, t, x = [int(v) for v in input().split()]
  norm_stx = [s - x, t - x, x]
  norm_stxn.append(norm_stx)
  
#歩行開始時間
dq = []
for i in range(q):
  qi = int(input())
  dq.append(qi)
iota = list(range(q))

#回答用配列
answers = [-1] * q  
  
#通行止め座標でインデックスを作る
#sorted_norm_s = sorted(norm_stxn, key=lambda norm_stx:norm_stx[0])
#sorted_norm_t = sorted(norm_stxn, key=lambda norm_stx:norm_stx[1])
sorted_norm_x = sorted(norm_stxn, key=lambda norm_stx:norm_stx[2])
#print(sorted_norm_x)

for norm_stx in sorted_norm_x:
  begin = bisect.bisect_left(dq, norm_stx[0])
  end = bisect.bisect_right(dq, norm_stx[1] - 1)
  for i in range(begin, end):
    answers[iota[i]] = norm_stx[2]
    
  del dq[begin:end]
  del iota[begin:end]
  
#for ans in answers:
#  print(ans)
print("\n".join([str(ans) for ans in answers]))

Submission status: Time Limit Exceeded

Solution code:
import bisect

#入力処理
n, q = [int(v) for v in input().split()]

#通行止め期間と座標
#座標1移動するのに時間1かかるので、期間から座標を引くとどの期間にスタートすると通行止めにかかるかというデータに変換できる
norm_stxn = []
for i in range(n):
  s, t, x = [int(v) for v in input().split()]
  norm_stx = [s - x, t - x, x]
  norm_stxn.append(norm_stx)
  
#歩行開始時間
dq = [int(input()) for i in range(q)]

  
#通行止め座標でソート
sorted_norm_x = sorted(norm_stxn, key=lambda norm_stx:norm_stx[2], reverse=True)
#print(sorted_norm_x)

inf_t = -1
sup_t = 10**9 + 1
sup_x = sup_t
mapping = [inf_t - sup_x, sup_t]
mapping_x = [-1, -1]

for norm_stx in sorted_norm_x:
  s, t, x = norm_stx
  left = bisect.bisect_left(mapping, s)
  right = bisect.bisect_right(mapping, t, lo=left)
  x_prev = mapping_x[right - 1]
  #del mapping[left:right]
  #del mapping_x[left:right]
  #mapping[left:left] = [s, t]
  #mapping_x[left:left] = [x, x_prev]
  
  mapping[left:right] = [s, t]
  mapping_x[left:right] = [x, x_prev]
  #mapping.insert(left, s)
  #mapping.insert(left + 1, t)
  #mapping_x.insert(left, x)
  #mapping_x.insert(left + 1, x_prev)
  
  #print(mapping)
  #print(mapping_x)
  #print("\n")

strbuf = []
prev_pos = 0
for di in dq:
  pos = bisect.bisect_right(mapping, di, lo=prev_pos)
  #print(mapping_x[pos - 1])
  strbuf.append(str(mapping_x[pos - 1]))
print("\n".join(strbuf))

Submission status: Time Limit Exceeded

Solution code:
import bisect

#入力処理
n, q = [int(v) for v in input().split()]

#通行止め期間と座標
#座標1移動するのに時間1かかるので、期間から座標を引くとどの期間にスタートすると通行止めにかかるかというデータに変換できる
norm_stxn = []
for i in range(n):
  s, t, x = [int(v) for v in input().split()]
  norm_stx = [s - x, t - x, x]
  norm_stxn.append(norm_stx)
  
#歩行開始時間
dq = [int(input()) for i in range(q)]

  
#通行止め座標でソート
sorted_norm_x = sorted(norm_stxn, key=lambda norm_stx:norm_stx[2], reverse=True)
#print(sorted_norm_x)

inf_t = -1
sup_t = 10**9 + 1
sup_x = sup_t
mapping = [inf_t - sup_x, sup_t]
mapping_x = [-1, -1]

for norm_stx in sorted_norm_x:
  s, t, x = norm_stx
  left = bisect.bisect_left(mapping, s)
  right = bisect.bisect_right(mapping, t, lo=left)
  x_prev = mapping_x[right - 1]
  #del mapping[left:right]
  #del mapping_x[left:right]
  #mapping[left:left] = [s, t]
  #mapping_x[left:left] = [x, x_prev]
  
  mapping[left:right] = [s, t]
  mapping_x[left:right] = [x, x_prev]
  #mapping.insert(left, s)
  #mapping.insert(left + 1, t)
  #mapping_x.insert(left, x)
  #mapping_x.insert(left + 1, x_prev)
  
  #print(mapping)
  #print(mapping_x)
  #print("\n")

  
prev_pos = 0
for di in dq:
  pos = bisect.bisect_right(mapping, di, lo=prev_pos)
  print(mapping_x[pos - 1])

Submission status: Time Limit Exceeded

Solution code:
import bisect

#入力処理
n, q = [int(v) for v in input().split()]

#通行止め期間と座標
#座標1移動するのに時間1かかるので、期間から座標を引くとどの期間にスタートすると通行止めにかかるかというデータに変換できる
norm_stxn = []
for i in range(n):
  s, t, x = [int(v) for v in input().split()]
  norm_stx = [s - x, t - x, x]
  norm_stxn.append(norm_stx)
  
#歩行開始時間
dq = [int(input()) for i in range(q)]

  
#通行止め座標でソート
sorted_norm_x = sorted(norm_stxn, key=lambda norm_stx:norm_stx[2], reverse=True)
#print(sorted_norm_x)

inf_t = -1
sup_t = 10**9 + 1
sup_x = sup_t
mapping = [inf_t - sup_x, sup_t]
mapping_x = [-1, -1]

for norm_stx in sorted_norm_x:
  s, t, x = norm_stx
  left = bisect.bisect_left(mapping, s)
  right = bisect.bisect_right(mapping, t, lo=left)
  x_prev = mapping_x[right - 1]
  del mapping[left:right]
  del mapping_x[left:right]
  
  #mapping.insert(left, s)
  #mapping.insert(left + 1, t)
  #mapping_x.insert(left, x)
  #mapping_x.insert(left + 1, x_prev)
  mapping[left:left] = [s, t]
  mapping_x[left:left] = [x, x_prev]
  
  #print(mapping)
  #print(mapping_x)
  #print("\n")

  
prev_pos = 0
for di in dq:
  pos = bisect.bisect_right(mapping, di, lo=prev_pos)
  print(mapping_x[pos - 1])

Submission status: Time Limit Exceeded

Solution code:
import bisect

#入力処理
n, q = [int(v) for v in input().split()]

#通行止め期間と座標
#座標1移動するのに時間1かかるので、期間から座標を引くとどの期間にスタートすると通行止めにかかるかというデータに変換できる
norm_stxn = []
for i in range(n):
  s, t, x = [int(v) for v in input().split()]
  norm_stx = [s - x, t - x, x]
  norm_stxn.append(norm_stx)
  
#歩行開始時間
dq = [int(input()) for i in range(q)]

  
#通行止め座標でソート
sorted_norm_x = sorted(norm_stxn, key=lambda norm_stx:norm_stx[2], reverse=True)
#print(sorted_norm_x)

inf_t = -1
sup_t = 10**9 + 1
sup_x = sup_t
mapping = [inf_t - sup_x, sup_t]
mapping_x = [-1, -1]

for norm_stx in sorted_norm_x:
  s, t, x = norm_stx
  left = bisect.bisect_left(mapping, s)
  right = bisect.bisect_right(mapping, t, lo=left)
  x_prev = mapping_x[right - 1]
  del mapping[left:right]
  del mapping_x[left:right]
  
  mapping.insert(left, s)
  mapping.insert(left + 1, t)
  mapping_x.insert(left, x)
  mapping_x.insert(left + 1, x_prev)
  
  #print(mapping)
  #print(mapping_x)
  #print("\n")

  
prev_pos = 0
for di in dq:
  pos = bisect.bisect_right(mapping, di, lo=prev_pos)
  print(mapping_x[pos - 1])

Submission status: Time Limit Exceeded

Solution code:
import bisect

#入力処理
n, q = [int(v) for v in input().split()]

#通行止め期間と座標
#座標1移動するのに時間1かかるので、期間から座標を引くとどの期間にスタートすると通行止めにかかるかというデータに変換できる
norm_stxn = []
for i in range(n):
  s, t, x = [int(v) for v in input().split()]
  norm_stx = [s - x, t - x, x]
  norm_stxn.append(norm_stx)
  
#歩行開始時間
dq = [int(input()) for i in range(q)]

  
#通行止め座標でソート
sorted_norm_x = sorted(norm_stxn, key=lambda norm_stx:norm_stx[2], reverse=True)
#print(sorted_norm_x)

inf_t = -1
sup_t = 10**9 + 1
sup_x = sup_t
mapping = [inf_t - sup_x, sup_t]
mapping_x = [-1, -1]

for norm_stx in sorted_norm_x:
  s, t, x = norm_stx
  left = bisect.bisect_left(mapping, s)
  right = bisect.bisect_right(mapping, t)
  x_prev = mapping_x[right - 1]
  del mapping[left:right]
  del mapping_x[left:right]
  
  mapping.insert(left, s)
  mapping.insert(left + 1, t)
  mapping_x.insert(left, x)
  mapping_x.insert(left + 1, x_prev)
  
  #print(mapping)
  #print(mapping_x)
  #print("\n")

  
for di in dq:
  pos = bisect.bisect_right(mapping, di)
  print(mapping_x[pos - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,Q = ints_raw()
    origST = []

    for idx  in range(N):
        S,T,X = ints_raw()
        origST.append([S-X,1,X])
        origST.append([T-X,-1,X])
    origST.sort()
    stidx = 0
    cur_set = set([])
    for idx in range(Q):
        q = int_raw()
        while stidx < len(origST):
            st = origST[stidx]
            if st[0] > q:
                break
            if st[1]>0:
                cur_set.add(st[2])
            else:
                cur_set.remove(st[2])
            stidx+=1
        if len(cur_set)==0:
            print(-1)
        else:
            print (min(cur_set))

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

#入力処理
n, q = [int(v) for v in input().split()]

#通行止め期間と座標
#座標1移動するのに時間1かかるので、期間から座標を引くとどの期間にスタートすると通行止めにかかるかというデータに変換できる
norm_stxn = []
for i in range(n):
  s, t, x = [int(v) for v in input().split()]
  norm_stx = [s - x, t - x, x]
  norm_stxn.append(norm_stx)
  
#歩行開始時間
dq = []
for i in range(q):
  qi = int(input())
  dq.append(qi)
iota = list(range(q))

#回答用配列
answers = [-1] * q  
  
#通行止め座標でインデックスを作る
#sorted_norm_s = sorted(norm_stxn, key=lambda norm_stx:norm_stx[0])
#sorted_norm_t = sorted(norm_stxn, key=lambda norm_stx:norm_stx[1])
sorted_norm_x = sorted(norm_stxn, key=lambda norm_stx:norm_stx[2])
#print(sorted_norm_x)

for norm_stx in sorted_norm_x:
  begin = bisect.bisect_left(dq, norm_stx[0])
  end = bisect.bisect_right(dq, norm_stx[1] - 1)
  for i in range(begin, end):
    answers[iota[i]] = norm_stx[2]
    
  del dq[begin:end]
  del iota[begin:end]
  
for ans in answers:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
#入力処理
n, q = [int(v) for v in input().split()]

#通行止め期間と座標
stxn = []
for i in range(n):
  stx = [int(v) for v in input().split()]
  stxn.append(stx)
  
#歩行開始時間
dq = []
for i in range(q):
  dq.append(int(input()))

#通行止めはソートされていないので座標でソートする
stxn_sorted = sorted(stxn, key=lambda stx:stx[2])

for di in dq:
  #通行止めに引っかかるかテスト
  for stxi in stxn_sorted:
    #diスタートでxiに到達する時間を計算し、その時間が通行止めだったらxiを出力
    time_on_xi = di + stxi[2] 
    if stxi[0] - 0.5 <= time_on_xi < stxi[1] - 0.5:
      #止まったのでxiを出力
      print(stxi[2])
      break
  else:
    #止まらなかったので-1を出力
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys
import bisect


class LazySegmentTree():

    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
        self.lazy = [0] * (2*self.size - 1)
        self.is_lazy = [False] * (2*self.size - 1)

       
    def lazy_eval(self, k, l, r):
        if self.is_lazy[k]:
            self.node[k] = self.lazy[k]
            if r - l > 1:
                self.lazy[2*k+1] = self.lazy[k]
                self.lazy[2*k+2] = self.lazy[k]
                self.is_lazy[2*k+1] = True
                self.is_lazy[2*k+2] = True
            self.is_lazy[k] = False

    def update(self, begin, end, val, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return
        if begin <= l and r <= end:
            self.lazy[k] = val
            self.is_lazy[k] = True
            self.lazy_eval(k, l, r)
        else:
            self.update(begin, end, val, 2*k+1, l, (l+r)//2)
            self.update(begin, end, val, 2*k+2, (l+r)//2, r) 
            self.node[k] = self.node[2*k+1] + self.node[2*k+2] 

    def get_sum(self, begin, end, k=0, l=0, r=-1):
        if r < 0:
            r = self.size
        self.lazy_eval(k, l, r)
        if r <= begin or end <= l:
            return 0
        if begin <= l and r <= end:
            return self.node[k]
        vl = self.get_sum(begin, end, 2*k+1, l, (l+r)//2)
        vr = self.get_sum(begin, end, 2*k+2, (l+r)//2, r)
        return vl + vr


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(sys.stdin.readline()) for i in range(q)]

coord_li = []
for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    coord_li += [a, b]
list1, compressed_memo, len_memo = compress(coord_li)

st = LazySegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)

for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    if st.get_sum(num-1, num) == 0:
        print(-1)
    else:
        print(info[st.get_sum(num-1, num)-1][2])

Submission status: Time Limit Exceeded

Solution code:
import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        it = bisect.bisect_left(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            del D[it]
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
d = [int(input()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
import bisect

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        it = bisect.bisect_left(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect


class DualSegmentTree():
 
    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)
 
    def update(self, begin, end, val, k=0, l=0, r=-1):
        if 2*self.size - 1 <= k:
            return
        if r < 0:
            r = self.size
        if begin <= l and r <= end:
            self.node[k] = min(val, self.node[k])
        self.update(begin, end, val, 2*k+1, l, (l+r)//2)
        self.update(begin, end, val, 2*k+2, (l+r)//2, r)

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
d = [int(input()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:

def BinarySearchLowerBound(_arr, _ele): # arr is strictly increasing
    low_ind = 0
    up_ind = len(_arr) - 1
    if _arr[low_ind] >= _ele:
        return low_ind
    if _arr[up_ind] <= _ele:
        return up_ind + 1
    found = None
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        if len(D) == 0:
            break
        it = BinarySearchLowerBound(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect


class DualSegmentTree():
 
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
 
    def update(self, begin, end, val, k=0, l=0, r=-1):
        if 2*self.size - 1 <= k:
            return
        if r < 0:
            r = self.size
        if begin <= l and r <= end:
            self.node[k] = max(val, self.node[k])
        self.update(begin, end, val, 2*k+1, l, (l+r)//2)
        self.update(begin, end, val, 2*k+2, (l+r)//2, r)

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = max(val, self.node[i])
        return val


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(input()) for i in range(q)]

coord_li = [info[i][0] - info[i][2] for i in range(n)] + [info[i][1] - info[i][2] for i in range(n)]
list1, compressed_memo, len_memo = compress(coord_li)

#番兵を置くために+1しておく
st = DualSegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)

for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    tmp = st.get_val(num-1)
    if tmp == 0:
        print(-1)
    else:
        print(info[tmp-1][2])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
S = []
T = []
X = []
D = []
for i in range(N):
    s,t,x = map(int, input().split())
    S.append(s)
    X.append(x)
    T.append(t)
for i in range(Q):
    D.append(int(input()))

flag = True
result = [0 for i in range(Q)]
for i in range(Q):
    for time in range(D[i],10**9):
        if max(X) < result[i]:
            result[i] = -1
            break
        for kouji in range(N):
            if (S[kouji]-0.5 <= time < T[kouji]-0.5) and (result[i] == X[kouji]):
                break
        else:
            result[i] += 1
            continue
        break


for i in result:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
S = []
T = []
X = []
D = []
for i in range(N):
    s,t,x = map(int, input().split())
    S.append(s)
    X.append(x)
    T.append(t)
for i in range(Q):
    D.append(int(input()))

flag = True
result = [0 for i in range(Q)]
for i in range(Q):
    for time in range(D[i],10**9):
        if max(T) < result[i]:
            result[i] = -1
            break
        for kouji in range(N):
            if (S[kouji]-0.5 <= time < T[kouji]-0.5) and (result[i] == X[kouji]):
                break
        else:
            result[i] += 1
            continue
        break


for i in result:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect


class DualSegmentTree():
 
    def __init__(self, n):
        self.size = 1
        INF = float("inf")
        while self.size < n:
            self.size *= 2
        self.node = [0] * (2*self.size - 1)
 
    def update(self, begin, end, val, k=0, l=0, r=-1):
        if 2*self.size - 1 <= k:
            return
        if r < 0:
            r = self.size
        if r <= begin or end <= l:
            pass
        if begin <= l and r <= end:
            self.node[k] = val
        self.update(begin, end, val, 2*k+1, l, (l+r)//2)
        self.update(begin, end, val, 2*k+2, (l+r)//2, r)


    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = max(val, self.node[i])
        return val


#座標圧縮したリストを返す
def compress(list1):
    list2 = sorted(set(list1))
    memo = {value : index for index, value in enumerate(list2)}
    return list2, memo, len(list2)


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info, key = itemgetter(2), reverse = True)
d = [int(input()) for i in range(q)]

coord_li = []
for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    coord_li += [a, b]
list1, compressed_memo, len_memo = compress(coord_li)

#番兵を置くために+1しておく
st = DualSegmentTree(len_memo + 1)

for i in range(n):
    a, b = info[i][0] - info[i][2] , info[i][1] - info[i][2]
    st.update(compressed_memo[a], compressed_memo[b], i+1)

for i in range(q):
    num = bisect.bisect_right(list1, d[i])
    if st.get_val(num-1) == 0:
        print(-1)
    else:
        print(info[st.get_val(num-1)-1][2])

Submission status: Time Limit Exceeded

Solution code:
import bisect, sys
input = sys.stdin.readline
N, Q = map(int,input().split())
E = []
append = E.append
for k in range(N):
    s, e, x = map(int,input().split())
    append([x,s-x,e-x])
D = [int(input()) for k in range(Q)]
E.sort()

ans = dict()
for d in D:
    ans[d] = -1
bi = bisect.bisect_left
for e in E:
    t = bi(D,e[1])
    while t < Q:
        if D[t] < e[2]:
            if ans[D[t]] == -1:
                ans[D[t]] = e[0]
            t += 1
        else:
            break

for k in range(Q):
    print(ans[D[k]])