Problem:


Score: 600 points

Problem Statement

M-kun is a brilliant air traffic controller.

On the display of his radar, there are N airplanes numbered 1, 2, ..., N, all flying at the same altitude.

Each of the airplanes flies at a constant speed of 0.1 per second in a constant direction. The current coordinates of the airplane numbered i are (X_i, Y_i), and the direction of the airplane is as follows:

if U_i is U, it flies in the positive y direction;

if U_i is R, it flies in the positive x direction;

if U_i is D, it flies in the negative y direction;

if U_i is L, it flies in the negative x direction.

To help M-kun in his work, determine whether there is a pair of airplanes that will collide with each other if they keep flying as they are now.

If there is such a pair, find the number of seconds after which the first collision will happen.

We assume that the airplanes are negligibly small so that two airplanes only collide when they reach the same coordinates simultaneously.

Constraints

1 \leq N \leq 200000

0 \leq X_i, Y_i \leq 200000

U_i is U, R, D, or L.

The current positions of the N airplanes, (X_i, Y_i), are all distinct.

N, X_i, and Y_i are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 U_1
X_2 Y_2 U_2
X_3 Y_3 U_3
:
X_N Y_N U_N

Output

If there is a pair of airplanes that will collide with each other if they keep flying as they are now, print an integer representing the number of seconds after which the first collision will happen.

If there is no such pair, print SAFE.

Sample Input 1

2
11 1 U
11 47 D

Sample Output 1

230

If the airplanes keep flying as they are now, two airplanes numbered 1 and 2 will reach the coordinates (11, 24) simultaneously and collide.  

Sample Input 2

4
20 30 U
30 20 R
20 10 D
10 20 L

Sample Output 2

SAFE

No pair of airplanes will collide.

Sample Input 3

8
168 224 U
130 175 R
111 198 D
121 188 L
201 116 U
112 121 R
145 239 D
185 107 L

Sample Output 3

100



Sample input:
2
11 1 U
11 47 D


Sample output:
230

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import io


def main():
    N = int( sys.stdin.readline() )

    XYU_list = []

    for _ in range(N):
        x,y,u = sys.stdin.readline().rstrip().split()
        XYU_list.append( [int(x),int(y),u] )

    
    check_UD = {}
    check_LR = {}

    check_UR = {}
    check_DL = {}
    check_UL = {}
    check_DR = {}


    for x,y,u in XYU_list:
        if (u == "U") or (u == "D"):
            check_UD.setdefault( x , [] )
            check_UD[x].append( (y,u) )
        
        if (u == "L") or (u == "R"):
            check_LR.setdefault( y , [] )
            check_LR[y].append( (x,u) )
        
        if (u == "U") or (u == "R"):
            check_UR.setdefault( (x+y) , [] )
            check_UR[ (x+y) ].append( (x,u) )

        if (u == "D") or (u == "L"):
            check_DL.setdefault( (x+y) , [] )
            check_DL[ (x+y) ].append( (x,u) )

        if (u == "U") or (u == "L"):
            check_UL.setdefault( (x-y) , [] )
            check_UL[ (x-y) ].append( (x,u) )

        if (u == "D") or (u == "R"):
            check_DR.setdefault( (x-y) , [] )
            check_DR[ (x-y) ].append( (x,u) )


    for check_dic in [check_UD, check_LR, check_UR, check_DL, check_UL, check_DR]:
        for key in check_dic:
            check_dic[key].sort()
    

    diff_min = float("inf")
    
    for arr in check_UD.values():
        for i in range(len(arr) - 1):
            if (arr[i][1] == "U") and (arr[i+1][1] == "D"):
                diff_min = min( diff_min, (arr[i+1][0] - arr[i][0]) / 2 )
    
    for arr in check_LR.values():
        for i in range(len(arr) - 1):
            if (arr[i][1] == "R") and (arr[i+1][1] == "L"):
                diff_min = min( diff_min, (arr[i+1][0] - arr[i][0]) / 2 )



    for arr in check_UR.values():
        for i in range(len(arr) - 1):
            if (arr[i][1] == "R") and (arr[i+1][1] == "U"):
                diff_min = min( diff_min, (arr[i+1][0] - arr[i][0]) )
    
    for arr in check_DL.values():
        for i in range(len(arr) - 1):
            if (arr[i][1] == "D") and (arr[i+1][1] == "L"):
                diff_min = min( diff_min, (arr[i+1][0] - arr[i][0]) )

    for arr in check_UL.values():
        for i in range(len(arr) - 1):
            if (arr[i][1] == "U") and (arr[i+1][1] == "L"):
                diff_min = min( diff_min, (arr[i+1][0] - arr[i][0]) )

    for arr in check_DR.values():
        for i in range(len(arr) - 1):
            if (arr[i][1] == "R") and (arr[i+1][1] == "D"):
                diff_min = min( diff_min, (arr[i+1][0] - arr[i][0]) )



    if diff_min != float("inf"):
        print( int(diff_min * 10) )
    else:
        print("SAFE")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def generate_test_case():
    import random
    random.seed(0)
    ret = list()
    n = 10
    for _ in range(5):
        plane_list = list()
        for _ in range(n):
            x, y = random.choices(range(200001), k=2)
            u = random.choice(['U', 'R', 'D', 'L'])
            plane_list.append((x, y, u))
        ret.append({
            'n': n,
            'plane_list': plane_list
        })
    return ret


def solve_simply(N, plane_list):
    # 1単位時間（5秒）ごとに衝突判定：O(N * max(X_1, Y_1, ..., X_N, Y_N))
    from collections import defaultdict
    occur_collision = False
    LIMIT_T = 200000 * 2
    t = 1
    while t <= LIMIT_T:
        location = defaultdict(int)
        same_location = False
        for plane in plane_list:
            x, y, u = plane
            x *= 2  # 移動単位が0.5なので2倍して格子点上に並べる
            y *= 2
            if u == 'U':
                y += t  # 座標はxy方向に2倍されているので速度は単位時間あたり1。
            elif u == 'R':
                x += t
            elif u == 'D':
                y -= t
            else:
                x -= t
            if location[(x, y)] > 0:
                same_location = True
                break
            location[(x, y)] += 1
        if same_location:
            occur_collision = True
            break
        t += 1
    if occur_collision:
        return t * 5
    else:
        return 'SAFE'


def get_min_t_on_same_line(N, plane_list, t_inf=2*(10**6)):
    import bisect
    from collections import defaultdict
    uy, dy = defaultdict(list), defaultdict(list)
    plane_list.sort(key=lambda p: (p[0], p[1]))  # sort by (x, y)
    for plane in plane_list:
        x, y, u = plane
        if u == 'U':
            uy[x].append(y)
        elif u == 'D':
            dy[x].append(y)
    lx, rx = defaultdict(list), defaultdict(list)
    plane_list.sort(key=lambda p: (p[1], p[0]))  # sort by (y, x)
    for plane in plane_list:
        x, y, u = plane
        if u == 'R':
            rx[y].append(x)
        elif u == 'L':
            lx[y].append(x)
    min_t = t_inf
    for y in rx.keys():  # 右向きの飛行機の対になる左向き飛行機の探索
        for x in rx[y]:
            index = bisect.bisect_right(lx[y], x)
            if index >= len(lx[y]):
                continue
            dist = lx[y][index] - x
            min_t = min(min_t, 5 * dist)
    for x in uy.keys():  # 上向きの飛行機の対になる下向き飛行機の探索
        for y in uy[x]:
            index = bisect.bisect_right(dy[x], y)
            if index >= len(dy[x]):
                continue
            dist = dy[x][index] - y
            min_t = min(min_t, 5 * dist)
    return min_t


def get_min_t_at_crossing(N, plane_list, t_inf=2*(10**6)):
    from collections import defaultdict
    import bisect
    plane_list.sort(key=lambda p: p[0])  # sort by x
    min_t = t_inf
    # (1) RU / LDの衝突：点をy+x=kのkで分類
    rx, ux = defaultdict(list), defaultdict(list)
    lx, dx = defaultdict(list), defaultdict(list)
    for plane in plane_list:
        x, y, u = plane
        k = y + x
        if u == 'U':
            ux[k].append(x)
        elif u == 'R':
            rx[k].append(x)
        elif u == 'D':
            dx[k].append(x)
        else:
            lx[k].append(x)
    for k in rx.keys():  # 右向きの飛行機の対になる上向き飛行機の探索
        for x in rx[k]:
            index = bisect.bisect_right(ux[k], x)
            if index >= len(ux[k]):
                continue
            x_diff = ux[k][index] - x
            min_t = min(min_t, 10 * x_diff)
    for k in dx.keys():  # 下向きの飛行機の対になる左向き飛行機の探索
        for x in dx[k]:
            index = bisect.bisect_right(lx[k], x)
            if index >= len(lx[k]):
                continue
            x_diff = lx[k][index] - x
            min_t = min(min_t, 10 * x_diff)
    # (2) RD / LUの衝突：点をy-x=kのkで分類
    rx, ux = defaultdict(list), defaultdict(list)
    lx, dx = defaultdict(list), defaultdict(list)
    for plane in plane_list:
        x, y, u = plane
        k = y - x
        if u == 'U':
            ux[k].append(x)
        elif u == 'R':
            rx[k].append(x)
        elif u == 'D':
            dx[k].append(x)
        else:
            lx[k].append(x)
    for k in rx.keys():  # 右向きの飛行機の対になる下向き飛行機の探索
        for x in rx[k]:
            index = bisect.bisect_right(dx[k], x)
            if index >= len(dx[k]):
                continue
            x_diff = dx[k][index] - x
            min_t = min(min_t, 10 * x_diff)
    for k in ux.keys():  # 上向きの飛行機の対になる左向き飛行機の探索
        for x in ux[k]:
            index = bisect.bisect_right(lx[k], x)
            if index >= len(lx[k]):
                continue
            x_diff = lx[k][index] - x
            min_t = min(min_t, 10 * x_diff)
    return min_t


def solve(N, plane_list):
    T_INF = 2 * (10 ** 6) + 1
    # 同一直線上での衝突の探索
    min_t = get_min_t_on_same_line(N, plane_list, T_INF)
    # クロス衝突の探索
    min_t = min(min_t, get_min_t_at_crossing(N, plane_list, T_INF))
    if min_t == T_INF:
        return 'SAFE'
    return min_t


def main():
    N = int(input())
    plane_list = list()
    for _ in range(N):
        X, Y, U = input().split()
        X, Y = int(X), int(Y)
        plane_list.append((X, Y, U))
    print(solve(N, plane_list))


def check():
    for i, test_case in enumerate(generate_test_case()):
        print('Check {}-th test case'.format(i))
        N, plane_list = test_case['n'], test_case['plane_list']
        assert solve_simply(N, plane_list) == solve(N, plane_list)
    print('OK')


if __name__ == '__main__':
    main()
    # check()

Submission status: Accepted

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

n = int(input())
C = [list(input().split()) for i in range(n)]

l = 2*10**5 + 5
# l = 100

# for jj in range(1000):
    # DD = ["U", "R", "D", "L"]
    # from random import randint
    # n = 10
    # l = 13
    # C = [[randint(0, 10) for j in range(2)] for i in range(n)]
    # C=[[10, 7, 'R'], [1, 9, 'U'], [9, 8, 'R'], [2, 5, 'U'], [4, 6, 'R'], [3, 9, 'U'], [10, 3, 'D'], [3, 6, 'L'], [6, 9, 'L'], [0, 8, 'U']]
    # C=[[2, 5, 'U'], [3, 6, 'L']]
    
    # for i in range(n):
    #     C[i].append(DD[randint(0,3)])
    # print(C)
    # co = 0
    # for i in range(n):
    #     for j in range(i+1,n):
    #         if C[i][:2] == C[j][:2]:
    #             co = 1
    # if co == 1:
    #     print("CONTINUE")
    #     continue

A = []
D = {"U": 0, "R": 1, "D": 2, "L": 3}
for i in range(n):
    A.append([int(C[i][0]), int(C[i][1]), D[C[i][2]]])

from bisect import bisect

ans = float("inf")
for ii in range(4):
    # print("ii",ii)
    # 正面衝突
    if ii <= 1:
        L = [[] for i in range(l)]
        R = [[] for i in range(l)]
        for i in range(n):
            if A[i][2] == 3:
                L[A[i][1]].append(A[i][0])
            if A[i][2] == 1:
                # print(A[i][0],A[i][1])
                R[A[i][1]].append(A[i][0])

        for i in range(l):
            R[i].sort()
            # print(L[i],R[i])
            for j in range(len(L[i])):
                ind = bisect(R[i], L[i][j])
                if ind > 0:
                    ans = min(ans, (L[i][j]-R[i][ind-1]) * 5)

    # 90度の衝突
    D = [[] for i in range(2*l)]
    L = [[] for i in range(2*l)]

    for i in range(n):
        if A[i][2] == 3:
            L[A[i][0] + A[i][1]].append(A[i][0])
        if A[i][2] == 2:
            D[A[i][0] + A[i][1]].append(A[i][0])
    for i in range(2*l):
        D[i].sort()
        for j in range(len(L[i])):
            ind = bisect(D[i], L[i][j])
            if ind > 0:
                ans = min(ans, (L[i][j]-D[i][ind-1]) * 10)
                # print("NEW", ans,L[i],D[i])

    for i in range(n):
        l2 = l // 2 - 1
        A[i][0], A[i][1] = (A[i][1]-l2) + l2, -(A[i][0]-l2) + l2
        A[i][2] = (A[i][2] + 1) % 4

if ans == float("inf"):
    ans = "SAFE"
print(ans)

    # eps = 10**-4
    # ans1 = float("inf")
    # for t in range(30):
    #     for i in range(n):
    #         if C[i][2] == "R":
    #             C[i][0] += 0.5
    #         elif C[i][2] == "L":
    #             C[i][0] -= 0.5
    #         elif C[i][2] == "D":
    #             C[i][1] -= 0.5
    #         else:
    #             C[i][1] += 0.5
    #     for i in range(n):
    #         for j in range(i+1, n):
    #             if abs(C[i][0] - C[j][0]) < eps and abs(C[i][1] - C[j][1]) < eps:
    #                 ans1 = (t+1)*5
    #                 print("CLASH",i,j, C[i][0],C[i][1])
    #     if ans1 != float("inf"):
    #         break
    # if ans1 == float("inf"):
    #     ans1 = "SAFE"

    # print(ans,ans1)
    # if ans != ans1:
    #     break

Submission status: Accepted

Solution code:
from operator import itemgetter
import bisect


n = int(input())
info = []
for i in range(n):
    x, y, u = input().split()
    info.append((int(x), int(y), u))
INF = 10 ** 18
ans = INF


info = sorted(info, key=itemgetter(0))
u = {}
d = {}
l = {}
r = {}
for x, y, dire in info:
    xy = x + y
    if dire == "U":
        if xy not in u:
            u[xy] = []
        u[xy].append(x)
    if dire == "D":
        if xy not in d:
            d[xy] = []
        d[xy].append(x)
    if dire == "L":
        if xy not in l:
            l[xy] = []
        l[xy].append(x)
    if dire == "R":
        if xy not in r:
            r[xy] = []
        r[xy].append(x)

for xy in u:
    if xy not in r:
        continue
    for x in u[xy]:
        ind = bisect.bisect_left(r[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[xy][ind]) * 10, ans)

for xy in l:
    if xy not in d:
        continue
    for x in l[xy]:
        ind = bisect.bisect_left(d[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - d[xy][ind]) * 10, ans)

info = sorted(info, key=itemgetter(0))
u = {}
d = {}
l = {}
r = {}
for x, y, dire in info:
    xy = x - y
    if dire == "U":
        if xy not in u:
            u[xy] = []
        u[xy].append(x)
    if dire == "D":
        if xy not in d:
            d[xy] = []
        d[xy].append(x)
    if dire == "L":
        if xy not in l:
            l[xy] = []
        l[xy].append(x)
    if dire == "R":
        if xy not in r:
            r[xy] = []
        r[xy].append(x)

for xy in d:
    if xy not in r:
        continue
    for x in d[xy]:
        ind = bisect.bisect_left(r[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[xy][ind]) * 10, ans)

for xy in l:
    if xy not in u:
        continue
    for x in l[xy]:
        ind = bisect.bisect_left(u[xy], x) - 1
        if ind < 0:
            continue
        ans = min((x - u[xy][ind]) * 10, ans)

l = {}
r = {}
for x, y, dire in info:
    if dire == "L":
        if y not in l:
            l[y] = []
        l[y].append(x)
    if dire == "R":
        if y not in r:
            r[y] = []
        r[y].append(x)

for y in l:
    if y not in r:
        continue
    for x in l[y]:
        ind = bisect.bisect_left(r[y], x) - 1
        if ind < 0:
            continue
        ans = min((x - r[y][ind]) * 5, ans)

info = sorted(info, key=itemgetter(1))
u = {}
d = {}
for x, y, dire in info:
    if dire == "U":
        if x not in u:
            u[x] = []
        u[x].append(y)
    if dire == "D":
        if x not in d:
            d[x] = []
        d[x].append(y)

for x in d:
    if x not in u:
        continue
    for y in d[x]:
        ind = bisect.bisect_left(u[x], y) - 1
        if ind < 0:
            continue
        ans = min((y - u[x][ind]) * 5, ans)

if ans == INF:
    print("SAFE")
else:
    print(ans)

Submission status: Accepted

Solution code:
import heapq
import copy
n = int(input())

size = 2*10**5
def f(ary):
    t_ans = 10**100
    for i in range(len(ary)):
        t_ud = ary[i]
        if len(t_ud) != 0:
            #print(t_ud)
            t_ud.sort()
            t_u = -10**100
            for j in range(len(t_ud)):
                if t_ud[j][1] == 'U':
                    t_u = t_ud[j][0]
                elif t_u == -10**100:
                    continue
                else:
                    t_ans = min(t_ans, (t_ud[j][0] - t_u))
    return t_ans

xyu = []

for i in range(n):
    x,y,u = input().split()
    x = int(x)
    y = int(y)
    xyu.append([x,y,u])

ud = [[] for i in range(size+1)]
rl = [[] for i in range(size+1)]
ul = [[] for i in range(size*2+1)]
ur = [[] for i in range(size*2+1)]
dl = [[] for i in range(size*2+1)]
dr = [[] for i in range(size*2+1)]

for i in range(n):
    if xyu[i][2] == 'U':
        ud[xyu[i][0]].append([xyu[i][1],'U'])
        ul[xyu[i][1]-xyu[i][0]+size].append([xyu[i][1],'U'])
        ur[xyu[i][1]+xyu[i][0]].append([xyu[i][1],'U'])
    if xyu[i][2] == 'D':
        ud[xyu[i][0]].append([xyu[i][1],'D'])
        dl[xyu[i][0]+xyu[i][1]].append([xyu[i][1],'D'])
        dr[xyu[i][1]-xyu[i][0]+size].append([xyu[i][1],'D'])
    if xyu[i][2] == 'R':
        rl[xyu[i][1]].append([xyu[i][0],'U'])
        ur[xyu[i][1]+xyu[i][0]].append([xyu[i][1],'D'])
        dr[xyu[i][1]-xyu[i][0]+size].append([xyu[i][1],'U'])
    if xyu[i][2] == 'L':
        rl[xyu[i][1]].append([xyu[i][0],'D'])
        ul[xyu[i][1]-xyu[i][0]+size].append([xyu[i][1],'D'])
        dl[xyu[i][0]+xyu[i][1]].append([xyu[i][1],'U'])
                  
ans = 10**100
ans = min(ans,f(ud)*5)
ans = min(ans,f(rl)*5)
ans = min(ans,f(ul)*10)
ans = min(ans,f(ur)*10)
ans = min(ans,f(dl)*10)
ans = min(ans,f(dr)*10)
if ans == 10**100:
    print('SAFE')
else:
    print(ans)

Submission status: Accepted

Solution code:
import heapq
import copy
n = int(input())

size = 2*10**5
def f(ary):
    t_ans = 10**100
    for i in range(len(ary)):
        t_ud = ary[i]
        if len(t_ud) != 0:
            #print(t_ud)
            t_ud.sort()
            t_u = -10**100
            for j in range(len(t_ud)):
                if t_ud[j][1] == 'U':
                    t_u = t_ud[j][0]
                elif t_u == -10**100:
                    continue
                else:
                    t_ans = min(t_ans, (t_ud[j][0] - t_u))
    return t_ans

xyu = []

for i in range(n):
    x,y,u = input().split()
    x = int(x)
    y = int(y)
    xyu.append([x,y,u])

ud = [[] for i in range(size+1)]
rl = [[] for i in range(size+1)]
ul = [[] for i in range(size*2+2)]
ur = [[] for i in range(size*2+2)]
dl = [[] for i in range(size*2+2)]
dr = [[] for i in range(size*2+2)]

for i in range(n):
    if xyu[i][2] == 'U':
        ud[xyu[i][0]].append([xyu[i][1],'U'])
        ul[xyu[i][1]-xyu[i][0]+size].append([xyu[i][1],'U'])
        ur[xyu[i][1]+xyu[i][0]].append([xyu[i][1],'U'])
    if xyu[i][2] == 'D':
        ud[xyu[i][0]].append([xyu[i][1],'D'])
        dl[xyu[i][0]+xyu[i][1]].append([xyu[i][1],'D'])
        dr[xyu[i][1]-xyu[i][0]+size].append([xyu[i][1],'D'])
    if xyu[i][2] == 'R':
        rl[xyu[i][1]].append([xyu[i][0],'U'])
        ur[xyu[i][1]+xyu[i][0]].append([xyu[i][1],'D'])
        dr[xyu[i][1]-xyu[i][0]+size].append([xyu[i][1],'U'])
    if xyu[i][2] == 'L':
        rl[xyu[i][1]].append([xyu[i][0],'D'])
        ul[xyu[i][1]-xyu[i][0]+size].append([xyu[i][1],'D'])
        dl[xyu[i][0]+xyu[i][1]].append([xyu[i][1],'U'])
                  
ans = 10**100
ans = min(ans,f(ud)*5)
ans = min(ans,f(rl)*5)
ans = min(ans,f(ul)*10)
ans = min(ans,f(ur)*10)
ans = min(ans,f(dl)*10)
ans = min(ans,f(dr)*10)
if ans == 10**100:
    print('SAFE')
else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XYUs = [list(map(str,input().split())) for _ in range(N)]

for i in range(len(XYUs)):
    XYUs[i][0] = int(XYUs[i][0])
    XYUs[i][1] = int(XYUs[i][1])


def check_the_conflict(XYUs):
    slopes = [[] for _ in range(400001)]
    for XYU in XYUs:
        if XYU[2] == "R" or XYU[2] == "D":       
            slopes[int(XYU[1])-int(XYU[0])+200000].append([int(XYU[0]),XYU[2]])    
    return slopes

def rotate_matrix(XYUs):
    converted = []
    for XYU in XYUs:
        if XYU[2] == "R":
            direction = "D"
        elif XYU[2] == "D":
            direction = "L"
        elif XYU[2] == "L":
            direction = "U"
        elif XYU[2] == "U":
            direction = "R"
        converted.append([XYU[1], 200000-XYU[0], direction])
    return converted
    
min_val = int(1e+10)

for i in range(4):
    if i > 0:
        XYUs = rotate_matrix(XYUs)
    slopes = check_the_conflict(XYUs)
    for slope in slopes:
        now_R = -int(1e+10)
        slope = sorted(slope)
        for airplane in slope:
            if airplane[1] == "R":
                now_R = airplane[0]
            elif airplane[1] == "D":
                candidate = (airplane[0] - now_R)*10
                if candidate < min_val:
                    min_val = candidate
    if i in [0,1]:
        rows = [[] for _ in range(200001)]
        for XYU in XYUs:
            rows[XYU[0]].append([XYU[1],XYU[2]])
        for row in rows:
            now_U = -int(1e+10)
            row = sorted(row)
            for airplane in row:
                if airplane[1] == "U":
                    now_U = airplane[0]
                elif airplane[1] == "D":
                    candidate = (airplane[0] - now_U)*5
                    if candidate < min_val:
                        min_val = candidate
if min_val < 3000000:
    print(min_val)
else:
    print("SAFE")

Submission status: Accepted

Solution code:
def x_ijo_min(lst, x):
    if lst[0] >= x: return lst[0]
    left = 0 # xより小さい
    right = len(lst) # x以上
    while left+1 < right:
        mid = (left+right) // 2
        if lst[mid] < x:
            left = mid
        else:
            right = mid
    if right == len(lst): return False
    else: return lst[right]

n = int(input())

dic_up = {}
dic_down = {}
dic_hor = {}
dic_ver = {}
lst = []
for i in range(n):
    xi, yi, ui = input().split()
    xi, yi = int(xi), int(yi)
    up = xi - yi
    down = xi + yi
    if (ui, up) in dic_up:
        dic_up[(ui, up)].append(xi)
    else:
        dic_up[(ui, up)] = [xi]
    if (ui, down) in dic_down:
        dic_down[(ui, down)].append(xi)
    else:
        dic_down[(ui, down)] = [xi]
    if (ui, xi) in dic_ver:
        dic_ver[(ui, xi)].append(yi)
    else:
        dic_ver[(ui, xi)] = [yi]
    if (ui, yi) in dic_hor:
        dic_hor[(ui, yi)].append(xi)
    else:
        dic_hor[(ui, yi)] = [xi]
    lst.append([xi, yi, ui, up, down])

for key in dic_up.keys():
    dic_up[key].sort()
for key in dic_down.keys():
    dic_down[key].sort()
for key in dic_hor.keys():
    dic_hor[key].sort()
for key in dic_ver.keys():
    dic_ver[key].sort()

ans = 10**9
for i in range(n):
    xi, yi, ui, up, down = lst[i]
    if ui == 'U':
        if ('D', xi) in dic_ver:
            dy = x_ijo_min(dic_ver[('D', xi)], yi)
            if dy: ans = min(ans, (dy-yi)*5)
        if ('L', up) in dic_up:
            lx = x_ijo_min(dic_up[('L', up)], xi)
            if lx: ans = min(ans, (lx-xi)*10)
    if ui == 'R':
        if ('U', down) in dic_down:
            ux = x_ijo_min(dic_down[('U', down)], xi)
            if ux: ans = min(ans, (ux-xi)*10)
        if ('D', up) in dic_up:
            dx = x_ijo_min(dic_up[('D', up)], xi)
            if dx: ans = min(ans, (dx-xi)*10)
        if ('L', yi) in dic_hor:
            lx = x_ijo_min(dic_hor[('L', yi)], xi)
            if lx: ans = min(ans, (lx-xi)*5)
    if ui == 'D':
        if ('L', down) in dic_down:
            lx = x_ijo_min(dic_down[('L', down)], xi)
            if lx: ans = min(ans, (lx-xi)*10)

if ans == 10**9:
    print('SAFE')
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


def culc(li):
    li.sort(key=lambda x: x[0])
    ans = 10**9
    for i in range(len(li)-1):
        if li[i][1] == '+' and li[i+1][1] == '-':
            ans = min(ans, li[i+1][0]-li[i][0])
    return ans


def main():
    N = int(input())
    axisX = defaultdict(list)
    axisY = defaultdict(list)
    XplusYplus = defaultdict(list)
    XminusYminus = defaultdict(list)
    XminusYplus = defaultdict(list)
    XplusYminus = defaultdict(list)
    ans = 10**9
    for _ in range(N):
        x, y, u = input().split()
        x, y = int(x), int(y)
        if u == 'U':
            axisY[x].append([y, '+'])
            XplusYplus[x+y].append([y-x, '+'])
            XminusYplus[x-y].append([x+y, '+'])
        elif u == 'R':
            axisX[y].append([x, '+'])
            XplusYplus[x+y].append([y-x, '-'])
            XplusYminus[x-y].append([x+y, '+'])
        elif u == 'D':
            axisY[x].append([y, '-'])
            XminusYminus[x+y].append([y-x, '-'])
            XplusYminus[x-y].append([x+y, '-'])
        elif u == 'L':
            axisX[y].append([x, '-'])
            XminusYminus[x+y].append([y-x, '+'])
            XminusYplus[x-y].append([x+y, '-'])

    for v in axisX.values():
        if len(v) > 1:
            ans = min(culc(v), ans)
    for v in axisY.values():
        if len(v) > 1:
            ans = min(culc(v), ans)
    for v in XplusYplus.values():
        if len(v) > 1:
            ans = min(culc(v), ans)
    for v in XplusYminus.values():
        if len(v) > 1:
            ans = min(culc(v), ans)
    for v in XminusYplus.values():
        if len(v) > 1:
            ans = min(culc(v), ans)
    for v in XminusYminus.values():
        if len(v) > 1:
            ans = min(culc(v), ans)
    print('SAFE' if ans > 10**8 else 5 * ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict

n = int(input())

xysame, upright, downright = {},{},{}
u_list = ("U","R","D","L")
for u in u_list:
    xysame[u] = defaultdict(list)
    upright[u] = defaultdict(list)
    downright[u] = defaultdict(list)

for _ in range(n):
    x,y,u = input().split()
    x,y = int(x),int(y)
    if u == "U" or u == "D":
        xysame[u][x].append(y)
    else:
        xysame[u][y].append(x)
    upright[u][y-x].append(x)
    downright[u][y+x].append(x)
    
for u in u_list:
    for key in xysame[u].keys():
        xysame[u][key].sort()
    for key in upright[u].keys():
        upright[u][key].sort()
    for key in downright[u].keys():
        downright[u][key].sort()

INF = 10**6
ans = INF


def line(low,high,type_ = 1):
    ret = INF
    for k,v in low.items():
        if high[k] == []: continue

        for vi in v:
            index = bisect_left(high[k], vi)
            if index == len(high[k]): continue
            ret = min(ret,(high[k][index]-vi)/type_)
    return ret

ans = min(ans, line(xysame["U"],xysame["D"],2))
ans = min(ans, line(xysame["R"],xysame["L"],2))
ans = min(ans, line(upright["R"],upright["D"],1))
ans = min(ans, line(upright["U"],upright["L"],1))
ans = min(ans, line(downright["R"],downright["U"],1))
ans = min(ans, line(downright["D"],downright["L"],1))

ans = int(ans*10)
if ans ==INF*10: ans = "SAFE"
    
print(ans)