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 queue


class Node(object):
    """docstring for Node"""

    def __init__(self, data=None):
        super(Node, self).__init__()
        self.data = data
        self.left = None
        self.right = None


class BST(object):
    """docstring for BST"""

    def __init__(self):
        super(BST, self).__init__()
        self.root = None

    '''Inorder Traversal'''

    def inorder(self, root):
        res = []
        if root:
            res = self.inorder(root.left)
            res.append(root.data)
            res = res + self.inorder(root.right)
        return res

    '''Finding an element in BST'''

    def find(self, data):
        if self.root is None:
            return 0
        curr = self.root
        while curr:
            if data == curr.data:
                return 1
            elif data < curr.data:
                curr = curr.left
            else:
                curr = curr.right
        return 0

    '''Finding min element in BST'''

    def findMin(self, root):
        if root is None:
            return 0
        root = self.root
        while root.left is not None:
            root = root.left
        return root.data

    '''Finding max element in BST'''

    def findMax(self, root):
        if root == None:
            return 0
        while root.right is not None:
            root = root.right
        return root.data

    '''Inserting an element in BST'''

    def insert(self, root, data):
        if root == None:
            root = Node(data)
        else:
            if data < root.data:
                root.left = self.insert(root.left, data)
            else:
                root.right = self.insert(root.right, data)
        return root

    '''Deleting an element in BST'''

    def delete(self, root, data):
        if root == None:
            return None
        elif data < root.data:
            root.left = self.delete(root.left, data)
        elif data > root.data:
            root.right = self.delete(root.right, data)
        else:
            # Node has two children
            if (root.left is not None) and (root.right is not None):
                temp = self.findMax(root.left)
                root.data = temp
                root.left = self.delete(root.left, root.data)
            else:
                if root.left:  # only left child
                    root = root.left
                elif root.right:  # only right child
                    root = root.right
                else:  # no child
                    root = None
        return root


n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s - x - 0.5, 1, x))
    event.append((t - x - 0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()

stop = BST()

ans = {}
for t, e, x in event:
    if e > 0:
        stop.root = stop.insert(stop.root, x)
    elif e < 0:
        stop.root = stop.delete(stop.root, x)
    else:
        if stop.root is not None:
            ans[x] = stop.findMin(stop.root)
        else:
            ans[x] = -1

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

Submission status: Time Limit Exceeded

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()
STX = [rl() for _ in range(N)]
D = rr(Q)[0]

STX.sort(key=lambda x: (x[2],x[0],x[1]))
STX = [[s-x,t-x,x] for s,t,x in STX]
for d in D:
    flag = 0
    for s,t,x in STX:
        if d < s:
            continue
        elif d < t:
            print(x)
            flag = 1
            break
    if flag == 0:
        print(-1)

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x-0.5, 1, x))
    event.append((t-x-0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()
stop = set()
ans = []
idx = []

for t,e,x in event:
    if e > 0:
        stop.add(x)
    elif e < 0:
        stop.remove(x)
    else:
        idx.append(x)
        if len(stop) > 0:
            ans.append(min(stop))
        else:
            ans.append(-1)

import numpy as np
ans = np.array(ans)[idx]
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x-0.5, 1, x))
    event.append((t-x-0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()
stop = set()
ans={}
for t,e,x in event:
    if e > 0:
        stop.add(x)
    elif e < 0:
        stop.remove(x)
    else:
        if len(stop) > 0:
            ans[x] = min(stop)
        else:
            ans[x] = -1

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

Submission status: Time Limit Exceeded

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

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
stop=set()
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
    elif e<0:
        stop.remove(x)
    elif len(stop)>0:
        ans[x]=min(stop)

print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        e = Event()
        e.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        e.type = 0 # evaluate
        e.pos = None
        e.idx = i
        l_event.append(e)

    # リストを時刻でソート O((N+Q)log(N+Q))
    l_event = sorted(l_event, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    minstop = 10**9 + 1

    # リストを順に処理する
    for e in l_event: #O(N+Q)
        if e.type == 1: # add
            s_stop.add(e.pos)
            if e.pos < minstop:
                minstop = e.pos
        elif e.type == -1: # delete
            s_stop.remove(e.pos)
            if minstop == e.pos:
                minstop = -1 # unknown state
        else: #evaluate
            if minstop == -1 or minstop == 10**9 + 1:
                if len(s_stop) != 0:
                    minstop = min(s_stop)
                    ans[e.idx] = minstop
            else:
                ans[e.idx] = minstop

    print("\n".join(map(str, ans)))

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    l_user = []
    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)

        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            if current_user_idx >= len(l_user):
                break
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    ans[u.idx] = min(s_stop) # O(log(2N))
                current_user_idx += 1
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
        else: # delete
            s_stop.remove(e.pos)

    print("\n".join([str(a) for a in ans]))

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

class Event:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        e = Event()
        e.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        e.type = 0 # evaluate
        e.pos = None
        e.idx = i
        l_event.append(e)

    # リストを時刻でソート O((N+Q)log(N+Q))
    l_event = sorted(l_event, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    # リストを順に処理する
    for e in l_event: #O(N+Q)
        if e.type == 1: # add
            s_stop.add(e.pos)
        elif e.type == -1: # delete
            s_stop.remove(e.pos)
        else: #evaluate
            if len(s_stop) != 0:
                ans[e.idx] = min(s_stop) # O(logN)
            else:
                pass

    print("\n".join([str(a) for a in ans]))

solve()

Submission status: Time Limit Exceeded

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

RW = []
for i in range(N):
    RW.append(list(map(int, input().split())))

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

RW.sort(key=lambda x:x[2])  # 工事中の座業でソート

for i in range(Q):  # Q人
    stop = False
    for j in range(N):  # N工事数
        if (RW[j][0] - 0.5 - D[i] <= RW[j][2]) and \
            (RW[j][1] - 0.5 - D[i] >= RW[j][2]):
            print(RW[j][2])
            stop = True
            break
    
    if not stop:
        print(-1)

Submission status: Time Limit Exceeded

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)

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

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

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

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 = bisect.bisect_left(blocked, value)
        blocked.insert(i, value)
    elif flag == 2:
        i = bisect.bisect_left(blocked, value)
        if i >= 0 and blocked[i] == value:
            del blocked[i]
    elif flag == 3:
        if len(blocked) > 0:
            dist[value] = blocked[0]

for d in dist:
    print d

Submission status: Time Limit Exceeded

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:
        blocked.append(value)
        blocked.sort()
    elif flag == 2:
        i = bisect.bisect_left(blocked, value)
        if i >= 0 and blocked[i] == value:
            del blocked[i]
    elif flag == 3:
        if len(blocked) > 0:
            dist[value] = blocked[0]

for d in dist:
    print d

Submission status: Time Limit Exceeded

Solution code:
import collections
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
Add = collections.defaultdict(set)
Elim = collections.defaultdict(set)
Times = set()
for stx in STX:
    s, t, x = stx
    Add[s - x].add(x)
    Elim[t - x].add(x)
    Times.add(s - x)
    Times.add(t - x)
Times = sorted(Times | set(D))
Block = set()
for time in Times:
    for x in Elim[time]:
        Block.remove(x)
    for x in Add[time]:
        Block.add(x)
    if time in D:
        if len(Block):
            print(min(Block))
        else:
            print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import numpy as np

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

list_in = []

D = []
for i in xrange(N):
    list_in.append(map(int,raw_input().split())
)

for i in xrange(Q):
    D.append(input())

list_in = np.array(list_in)
D = np.array(D)

sort_list = list_in[np.argsort(list_in[:, 2])]

cheakpoint = 0

for i in xrange(Q):
    flag = 0
    flag2 = 0
    for j in xrange(N):
        time = D[i]+sort_list[j][2]
        for k in xrange(j,N):
            if sort_list[k][2] > sort_list[j][2]:
                break
            if sort_list[k][2] == sort_list[j][2]:    
                if sort_list[k][0]<=time:
                    if sort_list[k][1]>time:
                        print (time-D[i])
                        flag = 1
                        break
                if k > 0:
                    flag2 = k

        if flag == 1:
            break
        if flag2 != 0:
            j = flag2

    if flag == 0:
        print -1

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 = {d:-1 for d in D}
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]])

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter


fin = sys.stdin.readline
N, Q = [int(elem) for elem in fin().split()]
stx = [[int(elem) for elem in fin().split()] for _ in range(N)]
stx = sorted(stx, key=itemgetter(2))
d_list = [int(fin()) for _ in range(Q)]


def pos_func(cur_t, d):
    # 時間とDから現在位置を返す関数
    return cur_t-d


def time_func(cur_x, d):
    # 位置とDから現在時間を返す関数
    return cur_x + d


def is_cross(d, s, t, x):
    if (x - pos_func(s, d)) * (x - pos_func(t, d)) <= 0:
        return True
    else:
        return False


for each_d in d_list:
    is_crossed = False
    for each_i in range(N):
        s, t, x = stx[each_i]
        s = s - 0.5
        t = t - 0.5
        # 交わるかの判定
        if is_cross(each_d, s, t, x):
            print(x)
            is_crossed = True
            break
    if not is_crossed:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys

input = sys.stdin.readline

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

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

    # print()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

    # print()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bisect
N,Q = map(int,input().split())
event = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

event.sort(key=lambda x:x[2])

ans = [-1]*Q
neg = [-1]*Q

for s,t,x in event:
    l = bisect(D,s-x)
    r = bisect(D,t-x)
    t = l
    while t < r:
        if neg[t] == -1:
            ans[t] = x
            neg[t] = r
            t += 1
        else:
            t = neg[t]

for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
#Dが (S-X) < D < (T-X) のときに地点Xでぶつかる
import bisect
from collections import OrderedDict
N, Q = map(int, input().split())

# 工事状況
L = []
for i in range(N):
    s, t, x = map(int, input().split())
    L.append((s-x, t-x, x))
# 工事状況を近い順にソート
L = sorted(L, key=lambda p:p[2])

# 人
D_ = []
for i in range(Q):
    D_.append((int(input()), i))
# 時刻順にソート
D_ = sorted(D_)
D = D_

# 距離を順次格納:
DD = [-1] * len(D)

# 工事を近い順に検索
# つまり、最初にヒットした工事でその人は止まる
for l in L:
    # その工事で止まる人を探索
    left = bisect.bisect_left(D, (l[0], 0))
    right = bisect.bisect_left(D, (l[1], 0))
    for d in D[left:right]:
        DD[d[1]] = l[2]
    # もう考慮しなくてよい人を取り除く
    del D[left:right]

# 出力
for d in DD:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
#Dが (S-X) < D < (T-X) のときに地点Xでぶつかる
import bisect
from collections import OrderedDict
N, Q = map(int, input().split())

# 工事状況
L = []
for i in range(N):
    s, t, x = map(int, input().split())
    L.append((s-x, t-x, x))
# 工事状況を近い順にソート
L = sorted(L, key=lambda p:p[2])

# 人
D_ = []
for i in range(Q):
    D_.append((int(input()), i))
# 時刻順にソート
D_ = sorted(D_)
# 二分探索できるようにOrderedDictに変換
D = OrderedDict()
for d in D_:
    D[d[0]] = d[1]

# 距離を順次格納:
DD = [-1] * len(D)

# 工事を近い順に検索
# つまり、最初にヒットした工事でその人は止まる
for l in L:
    # その工事で止まる人を探索
    distances = list(D.keys())
    left = bisect.bisect_left(distances, l[0])
    right = bisect.bisect_left(distances, l[1])
    for distance in distances[left:right]:
        DD[D[distance]] = l[2]
        # もう考慮しなくてよい人を取り除く
        del D[distance]

# 出力
for d in DD:
    print(d)

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], 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]
        lit = bisect.bisect_left(D, (Li, -1))
        rit = bisect.bisect_left(D, (Ri, -1))
        while lit < rit:
            ans[D[lit][1]] = Xi
            lit += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

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], 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]
        it = bisect.bisect_left(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            it += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

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 = [None] * Q
    for i in range(Q):
        D[i] = int(raw_input())
    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)
        while it < len(D):
            if D[it] >= Ri:
                break
            ans[it] = Xi
            it += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import bisect

def solve():
    N, Q = [int(_) for _ in input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(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:
import bisect

def solve():
    N, Q = [int(_) for _ in input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(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
            it += 1
    for i in range(Q):
        print (ans[i])

if __name__ == '__main__':
    solve()

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 xrange(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 xrange(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
            it += 1
    for i in xrange(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

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], 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
            it += 1
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
[n, q] = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for j in range(n)]
d = [int(input()) for i in range(q)]

l.sort(key=lambda x:x[2])

for i in d:
    for j in l:
        if (i + j[2] >= j[0]) and (i + j[2] < j[1]):
            print(j[2])
            break
        if (j == l[-1]):
            print(-1)
            break