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 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 e[1] <= 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 bisect, sys
input = sys.stdin.readline
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
for e in E:
    t = bisect.bisect_left(D,e[1])
    while t < Q:
        if e[1] <= 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:
from bisect import bisect_left
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 = sorted(E)
ans = dict()
for d in D:
    ans[d] = -1
for e in E:
    t = bisect_left(D,e[1])
    while t < Q:
        if e[1] <= 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 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
for e in E:
    t = bisect.bisect_left(D,e[1])
    while t < Q:
        if e[1] <= 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 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 = dict()
for d in D:
    ans[d] = -1
for e in E:
    t = bisect.bisect_left(D,e[1])
    while t < Q:
        if e[1] <= 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
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):
    s = bisect.bisect_left(d, cons[i][0])
    t = bisect.bisect_left(d, cons[i][1])
    while s < t:
        if ans[s] != -1:
            s += 1
        else:
            ans[s] = cons[i][2]
            s += 1
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

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

for d in list_d:
    retn = -1
    for x,s,t in list_xst:
        if ( (s <= d) and (t > d) ):
            retn = x
            break
    print(retn)

Submission status: Time Limit Exceeded

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

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

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

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

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

Solution code:
from bisect import bisect_left
from operator import itemgetter
import sys

input = sys.stdin.readline

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 = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for i, ans in enumerate(time[left:right]):
        if ans == -1:
            time[i+left] = x

for t in time:
    print(t)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from operator import itemgetter
import sys

input = sys.stdin.readline

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 = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            left += 1

for t in time:
    print(t)

Submission status: Time Limit Exceeded

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 = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for i, ans in enumerate(time[left:right]):
        if ans == -1:
            time[i+left] = x

for t in time:
    print(t)

Submission status: Time Limit Exceeded

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]:
        if time[q] == -1:
            time[q] = x
    if len(sorted_querys) == 0:
        break
for q in querys:
    print(time[q])

Submission status: Time Limit Exceeded

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[:left] + sorted_querys[right:]
    if len(sorted_querys) == 0:
        break
for q in querys:
    print(time[q])

Submission status: Time Limit Exceeded

Solution code:
import heapq as h
n,q = map(int, input().split())
tl = []
que = []
d = dict()
for _ in range(n):
  s,t,x = map(int, input().split())
  h.heappush(tl,[s-x,1,x])
  h.heappush(tl,[t-x,0,x])
for _ in range(q):
  t = int(input())
  que.append(t)
  h.heappush(tl,[t,2])
cur = set()
for _ in range(n*2+q):
  x = h.heappop(tl)
  if x[1] == 1:
    cur.add(x[2])
  if x[1] == 0:
    cur.remove(x[2])
  else:
    if cur:
      d[x[0]] = min(cur)
    else:
      d[x[0]] = -1
for i in que:
  print(d[i])

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
tl = []
que = []
d = dict()
for _ in range(n):
  s,t,x = map(int, input().split())
  tl.append([s-x,1,x])
  tl.append([t-x,0,x])
for _ in range(q):
  t = int(input())
  que.append(t)
  tl.append([t,2])
tl.sort()
cur = set()
for x in tl:
  if x[1] == 1:
    cur.add(x[2])
  if x[1] == 0:
    cur.remove(x[2])
  else:
    if cur:
      d[x[0]] = min(cur)
    else:
      d[x[0]] = -1
for i in que:
  print(d[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *

input = sys.stdin.readline

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

    ds = list(map(int, ss[n:]))
    ans = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        while i < q:
            if ds[i] < t:
                if ans[i] == -1:
                    ans[i] = x
                i += 1
            else:
                break

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

n, q = map(int, input().split())
ss = sys.stdin.readlines()
f(n, q, ss)

Submission status: Time Limit Exceeded

Solution code:
import sys
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 = []
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        ds.append(d)

    for x, s, t in xst:
        st = bisect_left(ds, s)
        for i in range(st, q):
            if ds[i] >= t:
                break
            if ans[i] == -1:
                ans[i] = x

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
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 = []
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        ds.append(d)

    for x, s, t in xst:
        st = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        for i in range(st, fi):
            if ans[i] == -1:
                ans[i] = x

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
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 = []
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        ds.append(d)

    for x, s, t in xst:
        i = bisect_left(ds, s)
        while i < q:
            if ds[i] < t:
                if ans[i] == -1:
                    ans[i] = x
                i += 1
            else:
                break

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

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

Submission status: Time Limit Exceeded

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())
        ds.append(d)
        dis.append([d, i])
    ds.sort()
    dis.sort()

    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("\n".join(map(str,ans)))


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

Submission status: Time Limit Exceeded

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())
        ds.append(d)
        dis.append([d, i])
    ds.sort()
    dis.sort()

    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,sep="\n")


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

Submission status: Time Limit Exceeded

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,sep="\n")


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

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, q = map(int, raw_input().split(" "))

events = []

for i in range(0, n):
    s, t, x = map(int, raw_input().split(" "))
    events.append(((s - x) * 10 + 0, 1, i, x))
    events.append(((t - x) * 10 + 1, 2, i, x))

for i in range(0, q):
    d = int(raw_input())
    events.append(((d * 10) + 2, 0, i, 0))

sort = sorted(events, key=lambda (a, b, c, d): a)
# print(sort)

ans = [-10 for i in range(0, q)]
const = set()
pos_index = [-1 for i in range(0, n)]
for i in range(0, len(sort)):
    key, state, index, pos = sort[i]
    if state == 1:
        const.add((pos, index))
        pos_index[index] = pos
    elif state == 2:
        #print("remove: %d" % pos_index[index])
        const.remove((pos_index[index], index))
    else:
        if len(const) <= 0:
            ans[index] = -1
        else:
            ans[index] = min(const)[0]
    #print(const)

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

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 *

result = {}

STX = sorted(STX, key=lambda x:x[2])
ds = D[:]

for s, t, x in STX:
    t1 = s - .5 - x
    t2 = t - .5 - x
    p1 = bisect_left(ds, t1)
    p2 = bisect_left(ds, t2)
    #print(p1, p2, t1, t2, ds[p1:p2])
    for d in ds[p1:p2]:
        result[d] = x
    ds = ds[:p1] + ds[p2:]

#print(result)

for d in D:
    print(result.get(d, -1))

Submission status: Time Limit Exceeded

Solution code:
def main():

    import sys
    input = sys.stdin.readline
    from bisect import bisect_left

    N,Q = map(int,input().split())
    info = []
    for _ in range(N):
        s,t,x = map(int,input().split())
        info.append((x,s,t))
    info = sorted(info)
    tmp = sorted([(int(input()),i) for i in range(Q)])
    D = []
    ID = []
    for d,i in tmp:
        D.append(d)
        ID.append(i)

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

    for x,s,t in info:
        left = bisect_left(D,s-x)
        right = bisect_left(D,t-x)
        for j in range(left,right):
            i = ID[j]
            if bit[i]:
                ans[i] = x
                bit[i] = 0

    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    import sys
    input = sys.stdin.readline
    from bisect import bisect_left

    N,Q = map(int,input().split())
    info = []
    for _ in range(N):
        s,t,x = map(int,input().split())
        info.append((x,s,t))
    info = sorted(info)
    tmp = sorted([(int(input()),i) for i in range(Q)])
    D = []
    ID = []
    for d,i in tmp:
        D.append(d)
        ID.append(i)

    S = set(range(Q))
    ans = [-1]*Q

    for x,s,t in info:
        left = bisect_left(D,s-x)
        right = bisect_left(D,t-x)
        for i in ID[left:right]:
            if i in S:
                ans[i] = x
                S.remove(i)

    for a in ans:
        print(a)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from bisect import bisect_left

    N,Q = map(int,input().split())
    info = [list(map(int,input().split())) for _ in range(N)]
    info.sort(key=lambda x:x[2])
    D = sorted([int(input()) for _ in range(Q)])
    nD = sorted([(d,i) for i, d in enumerate(D)])

    S = set(range(Q))
    ans = [-1]*Q

    for s,t,x in info:
        left = bisect_left(D,s-x)
        right = bisect_left(D,t-x)
        for d,i in nD[left:right]:
            if i in S:
                ans[i] = x
                S.remove(i)

    for a in ans:
        print(a)

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 _ in range(N)]
D = [int(input()) for _ in range(Q)]
Query = []
for s, t, x in STX:
    Query += [[s - x, 1, x], [t - x, -1, x]]
Query += [[D[_], 2, _] for _ in range(Q)]
Query.sort()
coord = set()
ans = []
for q in Query:
    if q[1] == 1:
        coord.add(q[2])
    elif q[1] == -1:
        coord.remove(q[2])
    else:
        if coord:
            ans += [[q[2], min(coord.copy())]]
        else:
            ans += [[q[2], -1]]
print(*(_[1] for _ in sorted(ans)), sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
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, 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 = 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.node[st.size-1+num-1]-1][2])

Submission status: Time Limit Exceeded

Solution code:
# [時間、変数、処理の種類]をイベントに追加。処理の種類は1：工事開始、2：工事終了、3：判定
from heapq import *
def f(n,q):
    events = []
    ans = [-1] * q
    koji = []
    set_koji = set()
    for _ in range(n):
        s, t, x = map(int, input().split())
        events += [[s - x - 0.3, x, 1]]
        events += [[t - x - 0.7, x, 2]]
    for i in range(q):
        d = int(input())
        events += [[d, i, 3]]
    events.sort()
    for j, h, s in events:
        if s == 1:
            heappush(koji, h)
            set_koji.add(h)
        elif s == 2:
            set_koji.remove(h)
        else:
            while koji:
                if koji[0] in set_koji:
                    break
                heappop(koji)
            if koji:
                ans[h] = koji[0]
    print(*ans, sep="\n")

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, raw_input().split(" "))

events = []

for i in range(0, n):
    s, t, x = map(int, raw_input().split(" "))
    events.append(((s - x) * 10 + 0, 1, i, x))
    events.append(((t - x) * 10 + 1, 2, i, x))

for i in range(0, q):
    d = int(raw_input())
    events.append(((d * 10) + 2, 0, i, 0))

sort = sorted(events, key=lambda (a, b, c, d): a)
# print(sort)

ans = [-10 for i in range(0, q)]
const = dict()
for i in range(0, len(sort)):
    key, state, index, pos = sort[i]
    if state == 1:
        const[index] = pos
    elif state == 2:
        const.pop(index)
    else:
        if const <= 0:
            ans[index] = -1
        else:
            if len(const) <= 0:
                ans[index] = -1
            else:
                ans[index] = min(const.values())


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

Submission status: Time Limit Exceeded

Solution code:
# [時間、変数、処理の種類]をイベントに追加。処理の種類は1：工事開始、2：工事終了、3：判定
from heapq import *
n, q = map(int, input().split())
events = []
ans = [-1] * q
koji = []
set_koji=set()
for _ in range(n):
    s, t, x = map(int, input().split())
    events += [[s - x - 0.3, x, 1]]
    events += [[t - x - 0.7, x, 2]]
for i in range(q):
    d = int(input())
    events += [[d, i, 3]]
events.sort()
for j, h, s in events:
    if s == 1:
        heappush(koji,h)
        set_koji.add(h)
    elif s == 2:
        set_koji.remove(h)
    else:
        while koji:
            if koji[0] in set_koji:
                break
            heappop(koji)
        if koji:
            ans[h] = koji[0]
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

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

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

event.sort()

closed = []
ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while closed and closed[0][1] <= d :
        heappop(closed)
    
    if closed :
        print(closed[0][0])
    else :
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

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

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

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

ei = 0

for d in D :
    while ei < N and event[ei][0] <= d :
        heapq.heappush(closed, (event[ei][2], event[ei][1]))
        ei += 1
    while len(closed) > 0 and closed[0][1] <= d :
        heapq.heappop(closed)
    
    if len(closed) == 0 :
        print(-1)
    else :
        print(closed[0][0])

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

event = []
for _ in range(N) :
    s, t, x = map(int, input().split())
    event.append([s - x, True, x])
    event.append([t - x, False, x])

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

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

ei = 0

for d in D :
    while ei < 2 * N and event[ei][0] <= d :
        if event[ei][1] :
            bisect.insort_left(constraction, event[ei][2])
        else :
            constraction.pop(bisect.bisect_left(constraction, event[ei][2]))
        ei += 1

    if len(constraction) == 0 :
        print(-1)
    else :
        print(min(constraction))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
 
 
N, Q = map(int, input().split(" "))
check_points = [input() for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = {}
for q in querys:
    time[q] = -1
b_left = bisect_left
for line in check_points:
    s, f, x = map(int, line.split(" "))
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    for q in querys[left:right]:
        if q >= end:
            break
        if time[q] == -1 or time[q] > x:
            time[q] = x
 
for q in querys:
    print(time[q])

Submission status: Time Limit Exceeded

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

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

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

for d in D :
    flag = True
    for s, t, x in STX :
        if s <= d < t :
            print(x)
            flag = False
            break
    if flag :
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			else:
				mini = min(kouho)
				if mini < 1000000001:
					print(mini)
				else:
					print(-1)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		for z in [None]*Q:
			if e[0] > d:
				if cont == True:
					if mini < 1000000001:
						print(mini)
					else:
						print(-1)
				else:
					mini = min(kouho)
					if mini < 1000000001:
						print(mini)
					else:
						print(-1)
			else:
				break
			cont = True
			if q < Q-1:
				q = q + 1
				d = int(inputs())
			else:
				flag = True
				q = q + 1
				break
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			cont = False
	for t in [None]*(Q-q):
		print(-1)
main()