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: Runtime Error

Solution code:
import sys
input =sys.stdin.readline
N,Q =map(int,input().split())
lis =[[int(i)for i in input().split()]for _ in range(N)]
basyo =[[int(input()),-1,-1,True] for _ in range(Q)]
lis = sorted(lis,key = lambda x:-x[2])
if basyo[0][0]!= 0:
    basyo.insert([0,-1,-1,False])
basyo.append([10**9+1,-1,-1,False])
#basyo = [[0,-1,-1],[10**9+1,-1,-1]]#[start,end]
def nibun(li,x):
    def hantei(numb):
        if li[numb][0]>x:
            return True
        else:
            return False
    left = -1
    right =len(li)
    while right - left != 1:
        med = (left+right)//2
        if hantei(med):
            right = med
        else:
            left = med
    return left

for posi in lis:
    X =max(posi[0]-posi[2],0)
    ind = nibun(basyo,X)
    if basyo[ind][0]!=X:
        basyo.insert(ind+1,[X,posi[2],-1,False])
    else:
        basyo[ind][1]=posi[2]
    X =max(posi[1]-1-posi[2],0)
    ind =nibun(basyo,X)
    if basyo[ind][0]!=X:
        basyo.insert(ind+1,[X,-1,posi[2],False])
    else:
        basyo[ind][2]=posi[2]
if basyo[0][1]==basyo[0][2]:
    basyo[0][1]=-1
for i,j in enumerate(basyo):
    if j[-1]:
        foo = max(j[1:3])
        if foo==-1:
            print(basyo[i-1][1])
        else:
            print(foo)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())

def getMN():
    return list(map(int, input().split()))

def getlist():
    return list(map(int, input().split()))
from bisect import bisect_left
import heapq
n, q = getlist()

sts = []
eds = []
for i in range(n):
    s, t, x = getlist()
    sts.append([s, t, x])

sts.sort(key = lambda x:(x[2]))
ds = []
for qr in range(q):
    point = getN()
    ds.append(point)

beg = []
points = [[] for i in range(len(ds))]
outs = [[] for i in range(len(ds))]
for st in sts:
    if st[1] - st[2] <= 0:
        beg.append(st[2])
    l = bisect_left(ds, st[1] - st[2])
    r = bisect_left(ds, st[0] - st[2])
    points[l].append(st[2])
    outs[r].append(st[2])

#print(points)
#print(outs)
q = []
tmp = -1
for b in beg:
    heapq.heappush(q, b)
if q:
    tmp = heapq.heappop(q)

answers = []
for idx, po in enumerate(points[::-1]):
    for value in po:
        heapq.heappush(q, value)
    #print(outs[idx])
    if tmp == -1 or tmp in outs[::-1][idx]:
        #print(q, tmp)
        if q:
            tmp = heapq.heappop(q)
        else:
            tmp = -1

    answers.append(tmp)

for a in answers[::-1]:
    print(a)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
W = [[] for i in range(2 * N)]
for i in range(0, 2 * N, 2):
  S, T, X = map(int, input().split())
  s = max(S - X, 0)
  t = max(T - X, 0)
  W[i] = [s, X]
  W[i + 1] = [t, -X]
W.sort()
A = []
minA = 10 ** 9
for i in range(Q):
  D = int(input())
  if len(W):
    while W[0][0] <= D:
      w = W.pop(0)
      if w[1] > 0:
        A.append(w[1])
        minA = min(w[1], minA)
      else:
        A.pop(A.index(-w[1]))
        if len(A) and minA == -w[1]:
          minA = min(A)
      if len(W) == 0:
        break
  print(minA if len(A) else -1)

Submission status: Runtime Error

Solution code:
import bisect
from operator import itemgetter

n, q = map(int, input().split())
stx = sorted([list(map(int, input().split())) for i in range(n)], key=itemgetter(2))
d = [int(input()) for i in range(q)]
stop = [-1 for i in range(q)]
did = 0
for i in stx:
    s = i[0] - i[2] - 0.5
    t = i[1] - i[2] - 0.5
    a = bisect.bisect_right(d[did:], t)
    b = bisect.bisect_right(d[did:], s)
    did += a - b
    for j in range(b + did, a + did):
        stop[j] = i[2]
for i in stop:
    print(i)

Submission status: Runtime Error

Solution code:
#include <iostream>
using namespace std;
int main(void){
    long n,m;
    cin>> n>>m;
    long t[n][3];
    for(int i=0;i<n;i++){
        cin >>t[i][0]>>t[i][1]>>t[i][2];
        // cout << t[i][0]<<t[i][1]<<t[i][2];
    }
    
    
    
    for(int i=0;i<m;i++){
        long man;
        cin >> man;
        long dist=10000000000;
        for(int j=0;j<n;j++){
            if(man+t[j][2]<t[i][0] or man+t[j][2]>=t[i][1]){
            }else{
                if(t[j][2] < dist){
                    dist = t[j][2];
                }
            }
            if(j==n-1 and dist==10000000000){
                cout <<-1<<endl;
            }else if(j==n-1){
                cout << dist << endl;
            }        
        }
    }
}

Submission status: Runtime Error

Solution code:
N,Q=(int(i) for i in input().split())
kouji=[]
for i in range(N):
    kouji.append([int(i) for i in input().split()])
    
for i in range(0,N):
    kouji[i].extend([kouji[i][0]-kouji[i][2],kouji[i][1]-kouji[i][2]])
kouji=sorted(kouji,key=lambda x:x[3])
D=[]
for i in range(Q):
    D.append(int(input()))



for q in range(Q):
    l=0
    t=1
    for i in kouji:
        if i[3]>=D[q] and i[4]=<D[q]:
            print(i[2])
            t=0
            break
    if t==1:
        print(-1)

Submission status: Runtime Error

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


blocks = list(map(int,input().split()) for _ in range(N))

z = sorted(set(s-x for s,t,x in blocks)+set(t-x for s,t,x in blocks))

D = [int(input()) for _ in range(Q)]

hits = [None]*len(z)
blocks.sort(key=lambda x: x[2])
n = list(range(1,N+1))

for s,t,x in blocks:
    s = bisect(z, s)
    t = bisect(z, t)
    
    nodes = []
    while s < t:
        nodes.append(s)
        hits[s] = x
        s = n(s)

    for node in nodes:
        n(node) = t

for d in D:
    print(hits[bisect(z, d)])

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
kouzi = []
for i in range(N):
    s,t,x = map(int,input().split())
    kouzi.append([s,t,x])
kouzi = sorted(kouzi, key=lambda x:(x[2]))
D = []
for j in range(Q):
    d = int(input())
    D.append(d)
kotae = [-1]*Q
yet = list(range(Q))
for k in kouzi:
    for h in yet:
        d = D[yet]
        hehen = ((k[0]-d)/k[2],(k[1]-d)/k[2])
        if hehen[0] <=  1 and hehen[1] > 1:
            kotae[h] = k[2]
            yet.remove(h)
for K in kotae:
    print(K)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
time = [0]
m_time = {}
m_time_inv = {}
time_info = []
info = []
for i in range(N):
	s,t,x = map(int,input().split())
	if t-x <= 0:
		continue
	time.append(t-x)
	time.append(max(0, s-x))
	info.append(-x,(max(0,s-x),t-x))
time = sorted(list(set(time)))
for i in range(len(time)):
	m_time[time[i]] = i
	m_time_inv[i] = time[i]
time_info = [-1 for i in time]
info.sort()
for i in info:
	x,s,t = i[0],i[1],i[2]
	for j in range(m_time[s], m_time[t]):
		time_info[j] = -x

def search(t):
	l,r = 0,len(time)
	while r-l > 1:
		p = (l+r)//2
		if t >= time[p]:
			l = p
		else:
			r = p
	return l

for q in range(Q):
	t = int(input())
	print(time_info[search(t)])

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def solve(n, q, liststx, listd):
    list1 = [-1 for _ in range(q)]   #q人の人リスト
    liststx.sort(key = lambda x:[x[2], x[0]])
    
    #key = 到達可能x, [start t, end t]を要素とするlist2
    list2 = defaultdict(lambda:[])
    
    for i in range(n):#i番目道路工事について
        x = liststx[i][2]
        start = liststx[i][0]-x
        end = liststx[i][1]-x
        list2[x] += [[start, end]]
    
    for x in list2.keys():
        for i in range(q):
            if list1[i] == -1:
                continue
            for j in range(len(list2[x])):
                if list2[x][j][0] <= listd[i] < list2[x][j][1]:
                    list1[i] = x
                    break
                    
    return list1
        
    
n, q = map(int, input().split())
liststx = []
for i in range(n):
    liststx += [list(map(int, input().split()))]
listd = [int(input()) for _ in range(n)]
ret = solve(n, q, liststx, listd)
for x in ret:
    print(x)

Submission status: Runtime Error

Solution code:
N, Q = list(map(int, input().split()))
dat=[]
for i in range(N):
  dat.append(list(map(int, input().split())))
for i in range(N):
  dat[i]=[dat[i][2],dat[i][0]-dat[i][2],dat[i][1]-dat[i][0]]
dat.sort(reverse=True)

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

dist=[-1]*(max(stt)+1)

for i in range(N):
  for j in range(dat[i][2]):
    if (dat[i][1]+j>=0) and (dat[i][1]+j<len(dist)):
      dist[dat[i][1]+j]=dat[i][0]
for i in range(Q):
  print(dist[stt[i]])

Submission status: Runtime Error

Solution code:
import bisect
N,Q=map(int,input().split())
K=[list(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
A=[-1 for i in range(Q)]
K.sort(key=lambda x:x[2],reverse=True)
for i in range(N):
  #工事はK[i][0]からK[i][1]-1まで
  #影響を受けるのはDがK[i][0]-K[i][2]からK[i][1]-1-K[i][2]まで
  s=K[i][0]-K[i][2]
  t=K[i][1]-1-K[i][2]
  j=bisect.bisect_left(D,s)
  while j<Q:
    while D[j]<=t:
      
      
      A[j]=K[i][2]
      j+=1
    break
for i in range(Q):
  print(A[i])

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
stops = [list(map(int, input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]
INF = 10 ** 9
res = [INF]*(max(D) + 1)

for stop in stops:
    d = stop[2]
    r = [i - d for i in range(stop[0], stop[1]) if i - d >= 0]
    for i in r:
        if i > max(D):
            break
        if res[i] > d:
            res[i] = d

for i in range(len(res)):
    if res[i] == INF:
        res[i] = -1

for d in D:
    print(res[d])

Submission status: Runtime Error

Solution code:
class Work:
    def __init__(self, time, x, f):
        self.time = time - x
        self.f = f
        self.x = x


def bin_search(lis, x):
    l = 0
    r = len(lis)
    while(True):
        m = (l+r)//2
        if (r-l <= 1):
            break
        elif (lis[m].time <= x.time):
            l = m
        else:
            r = m
    return m

def bin_search_x(lis, x):
    l = 0
    r = len(lis)
    while(True):
        m = (l+r)//2
        if (r-l <= 1):
            break
        elif (lis[m].x <= x.x):
            l = m
        else:
            r = m
    return m

n, q = map(int, input().split())
works = []
for i in range(n):
    s, t, x = map(int, input().split())
    works.append(Work(s, x, True))
    works.append(Work(t, x, False))

works = sorted(works, key = lambda w: w.time)


d = []
for i in range(q):
    d.append(int(input()))
    
workings = []
x_workings = []

while True:
    if works[0].time < d[0]:
        if works[0].f:
            w = works.pop(0)
            workings.append(workings, w)
            x_workings.insert(bin_search_x(x_workings, w)+1, w)
        else:
            w = works.pop(0)
            workings.pop(bin_search(workings, w))
            x_workings.pop(bin_search_x(x_workings, w))
    else:
        d.pop(0)
        if len(works) == 0:
            print(-1)
        else:
            print(x_workins[0].x)

Submission status: Runtime Error

Solution code:
import heapq

N, Q = map(int, input().split())

constructions = []
for _ in range(N):
    s, t, x = map(int, input().split())
    heapq.heappush(constructions, (x, s-x, t-x))

max_d = 0
D = [() for _ in range(Q)]
for i in range(Q):
    d = int(input())
    heapq.heappush(D, (d, i))
    D[i] = (d, i)
    max_d = max(max_d, d)

D.sort()
distance = [-1 for _ in range(Q)]
while constructions:
    x, s, t = heapq.heappop(constructions)
    if max_d < s or D[0][0] >= t:
        continue
    new_D = []
    for d, idx in D:
        if d >= s and d < t:
            distance[idx] = x
        else:
            new_D.append((d, idx))
    D = new_D
for d in distance:
    print(d)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
W = [[] for i in range(2 * N)]
for i in range(0, 2 * N, 2):
  S, T, X = map(int, input().split())
  s = max(S - X, 0)
  t = max(T - X, 0)
  W[i] = [s, X]
  W[i + 1] = [t, -X]
W.sort()
A = []
for i in range(Q):
  D = int(input())
  if len(W):
    while W[0][0] <= D:
      w = W.pop(0)
      if w[1] > 0:
        A.append(w[1])
        A.sort()
      else:
        A.pop(A.index(-w[1]))
      if len(W) == 0:
        break
  print(A[0] if len(A) else -1)