Problem:


Score : 500 points

Problem Statement

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

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

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

Find the distance each of the Q people will walk.

Constraints

All values in input are integers.

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

0 \leq S_i < T_i \leq 10^9

1 \leq X_i \leq 10^9

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2
2
10
-1
13
-1

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

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

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



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


Sample output:
2
2
10
-1
13
-1

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
STX = [tuple(map(int, input().split())) for _ in range(N)]
D = list(int(input()) for _ in range(Q))
for i, d in enumerate(D):
    ans = -1
    for s, t, x in STX:
        if s <= (x + d) < t:
            ans = x
            print(ans)
            break
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
STX = [[int(_) for _ in input().split()] for _ in range(N)]
STX = sorted(STX, key=lambda x:-x[2])
D = [int(input()) for _ in range(Q)]
eventlist = []
eventset = set()

for i in STX:
    S = i[0]
    T = i[1]
    X = i[2]
    eventlist.append([S-X, 1, X])
    eventlist.append([T-X, -1, X])

eventlist = sorted(eventlist, key=lambda x:x[0])

Dindex = 0
ans = [-1] * Q
for i in eventlist:
    x = i[2]
    if D[Dindex] < i[0]:
        if len(eventset) == 0:
            ans[Dindex] = -1
        else:
            ans[Dindex] = min(eventset)
        
        Dindex += 1
    
    if i[1] == 1:
        eventset.add(x)
    else:
        eventset.discard(x)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
STX = [[int(_) for _ in input().split()] for _ in range(N)]
STX = sorted(STX, key=lambda x:-x[2])
D = [int(input()) for _ in range(Q)]
eventlist = []
eventset = set()

for i in STX:
    S = i[0]
    T = i[1]
    X = i[2]
    eventlist.append([S-X, 1, X])
    eventlist.append([T-X, -1, X])

eventlist = sorted(eventlist, key=lambda x:x[0])

Dindex = 0
ans = [-1] * Q
for i in eventlist:
    x = i[2]
    if D[Dindex] < i[0]:
        if len(eventset) == 0:
            ans[Dindex] = -1
        else:
            ans[Dindex] = min(eventset)
        
        Dindex += 1
    
    if i[1] == 1:
        eventset.add(x)
    else:
        eventset.discard(x)

Submission status: Wrong Answer

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

STOP = []
for _ in range(N):
  s, t, x = map(int, input().strip().split(' '))
  tuple = (s + x, t + x, s, t, x)
  STOP.append(tuple)

COMPRESS = []
STOP = sorted(STOP)

len_stop = len(STOP)

a, b, s, t, x = STOP[0]
i = 1
while i < len_stop:
  a1, b1, s1, t1, x1 = STOP[i]
  i += 1
  if b1 <= b:
    pass
  else:
    COMPRESS.append((s, t, x))
    a = a1
    b = b1
    s = s1
    t = t1
    x = x1

COMPRESS.append((s, t, x))

D = [(i, -int(input().strip())) for i in range(Q)]

# print(STOP)
# print(COMPRESS)
RESULT = {i: -1 for i in range(len(D))}
for s, t, x in COMPRESS:
  remove_index = []
  for i, (q, d) in enumerate(D):
    if d + s <= x < d + t:
      RESULT[q] = x
      remove_index.append(i)
    if x > d + t:
      break

  for i0, i1 in enumerate(remove_index):
    del D[i1 - i0]

for _, v in sorted(RESULT.items()):
  print(v)

Submission status: Wrong Answer

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

STOP = []
for _ in range(N):
  s, t, x = map(int, input().strip().split(' '))
  tuple = (s + x, t + x, s, t, x)
  STOP.append(tuple)

COMPRESS = []
STOP = sorted(STOP)

len_stop = len(STOP)

a, b, s, t, x = STOP[0]
i = 1
while i < len_stop:
  a1, b1, s1, t1, x1 = STOP[i]
  i += 1
  if b1 <= b:
    pass
  else:
    COMPRESS.append((s, t, x))
    a = a1
    b = b1
    s = s1
    t = t1
    x = x1

COMPRESS.append((s, t, x))

D = [(i, -int(input().strip())) for i in range(Q)]

# print(STOP)
# print(COMPRESS)
RESULT = {i: -1 for i in range(len(D))}
for s, t, x in COMPRESS:
  remove_index = []
  for i, (q, d) in enumerate(D):
    if d + s <= x < d + t:
      RESULT[q] = x
      remove_index.append(i)
    elif x > d + t:
      break

for _, v in sorted(RESULT.items()):
  print(v)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append([s-x-0.5,1,x])
    TT.append([t-x-0.5,-1,x])
for i in range(Q):
    d = ri()
    TT.append([d,0,i])


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.discard(x)
        if mx == x:
            mx = INF
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append([s-x-0.5,1,x])
    TT.append([t-x-0.5,-1,x])
for _ in range(Q):
    d = ri()
    TT.append([d,0,0])


TT.sort()
mx = INF
mx_f = 0
for st,w,x in TT:
    if w == 1:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = 1
    elif w == -1:
        now.discard(x)
        if mx == x:
            mx = INF
            mx_f = 0
    else:
        if now == set():
            print(-1)
        else:
            if mx_f == 1:
                print(mx)
            else:
                mx = min(now)
                mx_f = 1
                print(mx)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append([s-x,1,x])
    TT.append([t-x,-1,x])
D = rr(Q)[0]

TT.sort()

d_ind = 0
d = D[d_ind]
for st,w,x in TT:
    if st > d:
        if now == set():
            print(-1)
        else:
            print(min(now))
        d_ind += 1
        if d_ind >= Q: break
        d = D[d_ind]
    if w==1:
        now.add(x)
    else:
        now.discard(x)
for i in range(d_ind,Q):
    print(-1)

Submission status: Wrong Answer

Solution code:
from ctypes import *
import subprocess as sp
from operator import itemgetter
import sys
import os.path

set_code = r"""
#include <set>

std::set<int> s;

void add(int x) {
    s.insert(x);
}

bool find(int x) {
    return s.find(x) != s.end();
}

void remove(int x) {
    s.erase(x);
}

bool empty() {
	return s.empty();
}

int getMin() {
	return *s.begin();
}
"""

class CppSet:
	counter = 0

	def __init__(self):
		lib_name = './hoge{}.so'.format(CppSet.counter)

		if not os.path.exists(lib_name):
			code_file_name = "tmp.cpp"
			with open(code_file_name, "w") as f:
				f.write(set_code)

			CppSet.counter += 1
			sp.Popen(['g++', '-fPIC', '-shared', '-std=c++11', code_file_name, '-o', lib_name]).communicate()

		lib = CDLL(lib_name)
		self.add = getattr(lib, "_Z3addi")
		self.find = CFUNCTYPE(c_bool, c_int)(
						("_Z4findi", lib),
						((1, "x"), )
					)
		self.remove = getattr(lib, "_Z6removei")
		self.empty = CFUNCTYPE(c_bool)(
						("_Z5emptyv", lib),
						()
					)

		self.getMin = CFUNCTYPE(c_int)(
						("_Z6getMinv", lib),
						()
					)

def main():
	N, Q = map(int, sys.stdin.readline().split())
	tmp = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
	stx = [(s - x, 1, x) for s, t, x in tmp] + [(t - x, -1, x) for s, t, x in tmp]
	stx.sort()
	
	D = [int(sys.stdin.readline()) for _ in range(Q)] 
	ans = [-1]*Q

	idx = 0
	stx_len = len(stx)
	se = CppSet()
	for i, d in enumerate(D):
		print(d)
		while idx < stx_len:
			t, com, x = stx[idx]
			if t > d:
				break
			if com == 1:
				se.add(x)
			else:
				se.remove(x)
			idx += 1
		ans[i] = (-1 if se.empty() else se.getMin())

	print(*ans, sep='\n')

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import bisect

N, Q = map(int, raw_input().split())
STX = [map(int, raw_input().split()) for i in range(N)]
D = [int(raw_input()) for i in range(Q)]

queue = []
queue += [(STX[i][0] - STX[i][2], 1, STX[i][2]) for i in range(N)]
queue += [(STX[i][1] - STX[i][2], 2, STX[i][2]) for i in range(N)]
queue += [(D[i], 3, i) for i in range(Q)]
queue.sort(key=lambda x:(x[0], x[1]))

dist = [-1] * Q
blocked = []
for t, flag, value in queue:
    if flag == 1:
        i = [i for i in range(len(blocked)) if blocked[i][0] == value]
        i = i[0] if len(i) > 0 else -1
        if i >= 0:
            blocked[i][1] += 1
        else:
            blocked.insert(i, [value, 1])
    elif flag == 2:
        i = [i for i in range(len(blocked)) if blocked[i][0] == value]
        i = i[0] if len(i) > 0 else -1
        if i >= 0 and blocked[i][0] == value:
            blocked[i][1] -= 1
            if blocked[i][1] == 0:
                del blocked[i]
    elif flag == 3:
        if len(blocked) > 0:
            dist[value] = blocked[0][0]

for d in dist:
    print d

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import sys

input = sys.stdin.readline

inf = float('inf')

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

events = []

for _ in range(N):
    s, t, x = map(int, input().split())
    add_event = (s - x, 1, x)
    remove_event = (t - x, -1, x)
    events.append(add_event)
    events.append(remove_event)

events.sort(key=itemgetter(0))  # イベント処理時刻昇順ソート

under_construction = set()

min_stop = inf

cur = 0
for _ in range(Q):
    d = int(input())
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        if event_type == 1:  # add_event
            under_construction.add(under_construction_x)
            min_stop = min(min_stop, under_construction_x)
        else:  # remove_event
            under_construction.discard(under_construction_x)
            if min_stop == under_construction_x:
                min_stop = inf
        cur += 1

    if min_stop == inf:
        if under_construction:
            min_stop = min(under_construction)
    print(min_stop if min_stop != inf else -1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import sys

input = sys.stdin.readline

inf = float('inf')

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

events = []

for _ in range(N):
    s, t, x = map(int, input().split())
    add_event = (s - x, 1, x)
    remove_event = (t - x, -1, x)
    events.append(add_event)
    events.append(remove_event)

events.sort(key=itemgetter(0))  # イベント処理時刻昇順ソート

under_construction = set()
min_stop = inf

cur = 0
for _ in range(Q):
    d = int(input())
    while cur < N * 2 and events[cur][0] <= d:
        exec_time, event_type, under_construction_x = events[cur]
        if event_type == 1:  # add_event
            under_construction.add(under_construction_x)
            min_stop = min(min_stop, under_construction_x)
        else:  # remove_event
            under_construction.discard(under_construction_x)
            if min_stop == under_construction_x:
                min_stop = inf
        cur += 1

    if min_stop == inf:
        min_stop = min(under_construction) if under_construction else inf
    print(min_stop if min_stop != inf else -1)

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
event = []
for i in range(N):
    s,t,x = map(int,input().split())
    event.append((s-x,x,1))
    event.append((t-x,x,-1))

s = set()

event.sort()
event.reverse()


for i in range(Q):
    D = int(input())
    f = False
    while event:
        t,x,e = event.pop()
        if D < t:
            f = True
            break
        if e == 1:
            s.add(x)
        else:
            s.remove(x)
    if len(s)==0:
        print(-1)
    else:
        print(min(s))
    if f:
        if e == 1:
            s.add(x)
        else:
            s.remove(x)

Submission status: Wrong Answer

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
    l = [None] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            if l[lit] is not None:
                lit = l[lit]
            else:
                ans[D[lit][1]] = Xi
                l[lit] = Ri
                lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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], reverse=True)
    # 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: Wrong Answer

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()

class MinGetSet:
    def __init__(self):
        self.values = set()
        self.min = None
    def getMin(self):
        if self.min is None:
            self.min = min(self.values) if self.values else None
        return self.min
    def add(self, v):
        self.values.add(v)
        if self.min is None or v < self.min:
            self.min = v
    def remove(self, v):
        self.values.remove(v)
        if self.min == v:
            self.min = None

s = MinGetSet()

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

Submission status: Wrong Answer

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()

class MinGetSet:
    def __init__(self):
        self.values = set()
        self.min = None
    def getMin(self):
        if self.min is None:
            self.min = min(self.values) if self.values else None
        return self.min if self.min is not None else -1
    def add(self, v):
        self.values.add(v)
        if self.min is None or v < self.min:
            self.min = v
    def remove(self, v):
        self.values.remove(v)
        if self.min == v:
            self.min = None

s = MinGetSet()

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

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
event = []
for i in range(N):
    s,t,x = map(int,input().split())
    event.append((s-x,x,1))
    event.append((t-x,x,-1))

s = set()

event.sort()


for i in range(Q):
    D = int(input())
    f = False
    while event:
        t,x,e = event.pop(0)
        if D < t:
            f = True
            break
        if e == 1:
            s.add(x)
        else:
            s.remove(x)
    if len(s)==0:
        print(-1)
    else:
        print(min(s))
    if f:
        if e == 1:
            s.add(x)
        else:
            s.remove(x)

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = float('inf')
N,Q = map(int,input().split())
event = []
for i in range(N):
    s,t,x = map(int,input().split())
    event.append((s-x-0.5,x,1,i))
    event.append((t-x-0.5,x,-1,i))

X_ = [INF]*N

event.sort()
event = deque(event)

for i in range(Q):
    D = int(input())
    while event:
        t,x,f,k = event.popleft()
        if D < t:
            break
        if f == 1:
            X_[k] = x
        else:
            X_[k] = INF
    ans = min(X_)
    if ans == INF:
        print(-1)
    else:
        print(ans)
    if f == 1:
        X_[k] = x
    else:
        X_[k] = INF

Submission status: Wrong Answer

Solution code:
from collections import deque
INF = float('inf')
N,Q = map(int,input().split())
event = []
for i in range(N):
    s,t,x = map(int,input().split())
    event.append((s-x,x,1,i))
    event.append((t-x,x,-1,i))

X_ = [INF]*N

event.sort()
event = deque(event)

for i in range(Q):
    D = int(input())
    while event:
        t,x,f,k = event.popleft()
        if D < t:
            break
        if f == 1:
            X_[k] = x
        else:
            X_[k] = INF
    ans = min(X_)
    if ans == INF:
        print(-1)
    else:
        print(ans)
    if f == 1:
        X_[k] = x
    else:
        X_[k] = INF

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
INF = float('inf')
N,Q = map(int,input().split())
event = []
for i in range(N):
    s,t,x = map(int,input().split())
    event.append((s-x,x,1,i))
    event.append((t-x,x,-1,i))
d = {}

X_ = [INF]*N

event.sort()
event = deque(event)

t,x,f,k = event.popleft()

for i in range(Q):
    D = int(input())
    while event:
        t,x,f,k = event.popleft()
        if D < t:
            break
        if f == 1:
            X_[k] = x
        else:
            X_[k] = INF
    ans = min(X_)
    if ans == INF:
        print(-1)
    else:
        print(ans)
    if f == 1:
        X_[k] = x
    else:
        X_[k] = INF

Submission status: Wrong Answer

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[end])
                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: Wrong Answer

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
    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: Wrong Answer

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()))

result = [0 for i in range(Q)]
for i in range(Q):
    for time in range(D[i],10**4):
        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: Wrong Answer

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],100):
        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: Wrong Answer

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)]
F = [D[k] for k in range(Q)]
E.sort()

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

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

Submission status: Wrong Answer

Solution code:
import bisect
N, Q = map(int,input().split())
E = []
for k in range(N):
    s, e, x = map(int,input().split())
    E.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

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

for q in ans:
    print(ans[q])

Submission status: Wrong Answer

Solution code:
import bisect
N, Q = map(int,input().split())
C = [list(map(int,input().split())) for k in range(N)]
D = [int(input()) for k in range(Q)]

E = []
for c in C:
    s, e, x = c[0], c[1], c[2]
    E.append([x,s-x,e-x])
E.sort()

ans = []
U = [0 for k in range(Q)]
c = 0
for e in E:
    t = bisect.bisect_left(D,e[1])
    while t < Q:
        if D[t] <= e[2]:
            ans.append(e[0])
            D.pop(t)
            U[c+t] = 1
            t += 1
            c += 1
            Q -= 1
        else:
            break

for k in range(Q+c):
    if U[k] == 1:
        print(ans.pop(0))
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import bisect
N, Q = map(int,input().split())
C = [list(map(int,input().split())) for k in range(N)]
D = [int(input()) for k in range(Q)]

E = []
for c in C:
    s, e, x = c[0], c[1], c[2]
    E.append([x,s-x,e-x])
E.sort()

ans = []
U = [0 for k in range(Q)]
c = 0
for e in E:
    t = bisect.bisect_left(D,e[1])
    while t < Q:
        if D[t] < e[2]:
            ans.append(e[0])
            D.pop(t)
            U[c+t] = 1
            t += 1
            c += 1
            Q -= 1
        else:
            break

for k in range(Q+c):
    if U[k] == 1:
        print(ans.pop(0))
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
input = sys.stdin.readline

n, q = map(int, input().split())
cons = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

cons.sort(key=lambda x: x[2])
for i in range(n):
    cons[i][0] -= cons[i][2]
    cons[i][1] -= cons[i][2]

ans = [-1] * q
for i in range(n - 1, -1, -1):
    s = bisect.bisect_left(d, cons[i][0])
    t = bisect.bisect_left(d, cons[i][1])
    if s <= q - 1 and t <= q - 1 and s < t:
        ans[s:t] = [cons[i][2]] * (t - s)
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
import bisect
input = sys.stdin.readline

n, q = map(int, input().split())
cons = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

cons.sort(key=lambda x: x[2])
for i in range(n):
    cons[i][0] -= cons[i][2]
    cons[i][1] -= cons[i][2]

ans = [-1] * q
for i in range(n - 1, -1, -1):
    s = bisect.bisect_left(d, cons[i][0])
    t = bisect.bisect_left(d, cons[i][1])
    if s <= q - 1 and t <= q - 1 and s <= t:
        ans[s:t] = [cons[i][2]] * (t - s)
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import bisect
n, q = map(int, input().split())
cons = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

cons.sort(key=lambda x: x[2])
for i in range(n):
    cons[i][0] -= cons[i][2]
    cons[i][1] -= cons[i][2]

ans = [-1] * q
for i in range(n - 1, -1, -1):
    s = bisect.bisect_left(d, cons[i][0])
    t = bisect.bisect_left(d, cons[i][1])
    if s <= q - 1 and t <= q - 1:
        ans[s:t] = [cons[i][2]] * (t - s)
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import bisect
n, q = map(int, input().split())
cons = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

cons.sort(key=lambda x: x[2])
for i in range(n):
    cons[i][0] -= cons[i][2]
    cons[i][1] -= cons[i][2]

ans = [-1] * q
for i in range(n - 1, -1, -1):
    s = bisect.bisect_left(d, cons[i][0])
    t = bisect.bisect_left(d, cons[i][1])
    if s <= q - 1 and t <= q - 1:
        ans[s:t] = [cons[i][2]] * (t - s)
print(ans)

Submission status: Wrong Answer

Solution code:
n,q = list(map(int, input().split()))

list_xst = []
for _ in range(n):
    s,t,x = list(map(int, input().split()))
    list_xst.append([x, s-x, t-x])

list_xst.sort(key=lambda l:l[0])

list_d = [int(input()) for _ in range(q)]

print(list_d)

for d in list_d:
    retn = -1
    for xst in list_xst:
        if ( (xst[1] <= d) and (xst[2] > d) ):
            retn = xst[0]
            break
    print(retn)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
sorted_querys = sorted(querys)
check_points = sorted(check_points, key=itemgetter(2))
for q in querys:
    time[q] = -1
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(sorted_querys, start)
    right = b_left(sorted_querys, end)
    for q in sorted_querys[left:right]:
        time[q] = x
    sorted_querys = sorted_querys[right:]
    if len(sorted_querys) == 0:
        break
for q in querys:
    print(time[q])

Submission status: Wrong Answer

Solution code:
# youtubeバージョン
import sys
from heapq import *
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    dis=[]
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        heappush(ds,d)
        heappush(dis, [d, i])


    for x, s, t in xst:
        i=bisect_left(ds,s)
        nd=len(ds)
        while i<nd:
            if ds[i]<t:
                ai=dis[i][1]
                ans[ai]=x
                del ds[i]
                del dis[i]
                nd-=1
            else:
                break

    print(ans)


n, q = map(int, input().split())
f(n, q)