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

Solution code:
N = int(input())
U = []
D = []
R = []
L = []
ans = []

for n in range(N):
  X,Y,Z = input().split()
  X = int(X)
  Y = int(Y)
  if Z=="U":
    U+=[[X,Y]]
  elif Z=="D":
    D+=[[X,Y]]
  elif Z=="R":
    R+=[[X,Y]]
  else:
    L+=[[X,Y]]

for x1,y1 in U:
  for x2,y2 in D:
    if x1==x2 and y1<y2:
      ans+=[5*abs(y1-y2)]

for x1,y1 in U:
  for x2,y2 in R:
    if 0<x1-x2==y2-y1:
      ans+=[10*(x1-x2)]

for x1,y1 in U:
  for x2,y2 in L:
    if 0<x2-x1==y2-y1:
      ans+=[10*(x2-x1)]

for x1,y1 in D:
  for x2,y2 in R:
    if 0<x1-x2==y1-y2:
      ans+=[10*(x1-x2)]

for x1,y1 in D:
  for x2,y2 in L:
    if 0<x2-x1==y1-y2:
      ans+=[10*(x2-x1)]

for x1,y1 in R:
  for x2,y2 in L:
    if y1==y2 and x1<x2:
      ans+=[5*abs(x1-x2)]

if len(ans)==0:
  print("SAFE")
else:
  print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect_right
N = int(input())
XYU = [None]*N
for i in range(N):
    x, y, u = input().split()
    XYU[i] = (int(x), int(y), u)
U, D = defaultdict(list), defaultdict(list)
R, L = defaultdict(list), defaultdict(list) 
Ru, Rd, Lu, Ld = defaultdict(list), defaultdict(list), defaultdict(list), defaultdict(list)
for x, y, u in XYU:
    if u == 'R':
        Ru[x+y].append(x)
        Rd[y-x].append(x)
        R[y].append(x)
    elif u == 'L':
        Lu[y-x].append(x)
        Ld[x+y].append(x)
        L[y].append(x)
    elif u == 'U':
        U[x].append(y)
    else:
        D[x].append(y)
ans = float('inf')
for x in U:
    if len(D[x]) > 0:
        D[x].sort()
        le = len(D[x])
        for y in U[x]:
            idx = bisect_right(D[x], y)
            if idx < le and ans > (D[x][idx]-y)/2:
                ans = (D[x][idx]-y)/2
for y in R:
    if len(L[y]) > 0:
        L[y].sort()
        le = len(L[y])
        for x in R[y]:
            idx = bisect_right(L[y], x)
            if idx < le and ans > (L[y][idx]-x)/2:
                ans = (L[y][idx]-x)/2
for x, y, u in XYU:
    if u == 'U':
        if len(Ru[x+y]) > 0:
            for _x in Ru[x+y]:
                if _x < x and ans > x-_x:
                    ans = x-_x
        if len(Lu[y-x]) > 0:
            for _x in Lu[y-x]:
                if x < _x and ans > _x-x:
                    ans = _x-x
    elif u == 'D':
        if len(Rd[y-x]) > 0:
            for _x in Rd[y-x]:
                if x > _x and ans > x-_x:
                    ans = x-_x
        if len(Ld[x+y]) > 0:
            for _x in Ld[x+y]:
                if x < _x and ans > _x-x:
                    ans = _x-x
if ans == float('inf'):
    print('SAFE')
else:
    print(int(ans*10))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

from collections import defaultdict

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

forward_diag = defaultdict(list)
backward_diag = defaultdict(list)
updown = defaultdict(list)
leftright = defaultdict(list)

elems = []
N = int(input())
for _ in range(N):
    x, y, U = input().split(' ')
    x = int(x)
    y = int(y)
    U
    elems += [(x, y, U)]

N = len(elems)


for x, y, U in elems:
    forward_diag[x-y] += [(x, U)]
    backward_diag[x+y] += [(x, U)]
    updown[x] += [(y, U)]
    leftright[y] += [(x, U)]

min_collisions = float("inf")

def search(lst, A, B):
    ret = float("inf")
    lst = sorted([(a, d) for (a, d) in lst])
    i = 0
    while i < len(lst):
        while i < len(lst) and lst[i][1] != A:
            i += 1
        j = i
        while j < len(lst) and lst[j][1] != B:
            j += 1
        if i < len(lst) and j < len(lst):
            ret = min(ret, lst[j][0]-lst[i][0])
        i += 1
    return ret

for lst in updown.values():
    min_collisions = min(min_collisions, 5*search(lst, 'U', 'D'))
for lst in leftright.values():
    min_collisions = min(min_collisions, 5*search(lst, 'R', 'L'))
for lst in forward_diag.values():
    min_collisions = min(min_collisions, 10*search(lst, 'U', 'L'))
    min_collisions = min(min_collisions, 10*search(lst, 'R', 'D'))
for lst in backward_diag.values():
    min_collisions = min(min_collisions, 10*search(lst, 'R', 'U'))
    min_collisions = min(min_collisions, 10*search(lst, 'D', 'L'))

if min_collisions == float("inf"):
    print("SAFE")
else:
    print(min_collisions)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xyu_180_1 = {}
xyu_180_2 = {}
xyu_90_1 = {}
xyu_90_2 = {}
xyu_90_3 = {}
xyu_90_4 = {}
for i in range(n):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    if u == "U":
        xyu_180_2.setdefault(x, {"U":[], "D":[]})
        xyu_180_2[x][u].append(y)
        xyu_90_1.setdefault(x + y, {"R":[], "U":[]})
        xyu_90_1[x + y][u].append(x - y)
        xyu_90_2.setdefault(x - y, {"U":[], "L":[]})
        xyu_90_2[x - y][u].append(x + y)
    elif u == "R":
        xyu_180_1.setdefault(y, {"R":[], "L":[]})
        xyu_180_1[y][u].append(x)
        xyu_90_1.setdefault(x + y, {"R":[], "U":[]})
        xyu_90_1[x + y][u].append(x - y)
        xyu_90_4.setdefault(x - y, {"D":[], "R":[]})
        xyu_90_4[x - y][u].append(x + y)
    elif u == "D":
        xyu_180_2.setdefault(x, {"U":[], "D":[]})
        xyu_180_2[x][u].append(y)
        xyu_90_3.setdefault(x + y, {"L":[], "D":[]})
        xyu_90_3[x + y][u].append(x - y)
        xyu_90_4.setdefault(x - y, {"D":[], "R":[]})
        xyu_90_4[x - y][u].append(x + y)
    elif u == "L":
        xyu_180_1.setdefault(y, {"R":[], "L":[]})
        xyu_180_1[y][u].append(x)
        xyu_90_2.setdefault(x - y, {"U":[], "L":[]})
        xyu_90_2[x - y][u].append(x + y)
        xyu_90_3.setdefault(x + y, {"D":[], "L":[]})
        xyu_90_3[x + y][u].append(x - y)
time = float("inf")
for i in xyu_180_1.values():
    if i["R"] and i["L"]:
        for j in i["R"]:
            for k in i["L"]:
                temp = (k - j) * 5
                if temp > 0:
                    time = min(time, temp)
for i in xyu_180_2.values():
    if i["U"] and i["D"]:
        for j in i["U"]:
            for k in i["D"]:
                temp = (k - j) * 5
                if temp > 0:
                    time = min(time, temp)
for i in xyu_90_1.values():
    if i["R"] and i["U"]:
        for j in i["R"]:
            for k in i["U"]:
                temp = (k - j) * 5
                if temp > 0:
                    time = min(time, temp)
for i in xyu_90_2.values():
    if i["U"] and i["L"]:
        for j in i["U"]:
            for k in i["L"]:
                temp = (k - j) * 5
                if temp > 0:
                    time = min(time, temp)
for i in xyu_90_3.values():
    if i["D"] and i["L"]:
        for j in i["D"]:
            for k in i["L"]:
                temp = (k - j) * 5
                if temp > 0:
                    time = min(time, temp)
for i in xyu_90_4.values():
    if i["R"] and i["D"]:
        for j in i["R"]:
            for k in i["D"]:
                temp = (k - j) * 5
                if temp > 0:
                    time = min(time, temp)
if time == float("inf"):
    print("SAFE")
else:
    print(time)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()


keys = ['D', 'L', 'R', 'U']
coords = {}
for key in keys:
    coords[key] = []

n = int(input())
for _ in range(n):
    x, y, u = input().split(" ")
    coords[u].append([int(x)*10, int(y)*10])

out = None
for ki1, key1 in enumerate(keys):
    coords1 = coords[key1]
    for x1, y1 in coords1:

        for key2 in keys[ki1+1:]:
            coords2 = coords[key2]

            for x2, y2 in coords2:
                cur_time = None
                if key1 == "D" and key2 == "R":
                    d1 = y1 - y2
                    d2 = x1 - x2
                    if d1 > 0 and d2 > 0 and d1 == d2:
                        cur_time = d1
                elif key1 == "D" and key2 == "L":
                    d1 = y1 - y2
                    d2 = x2 - x1
                    if d1 > 0 and d2 > 0 and d1 == d2:
                        cur_time = d1
                elif key1 == "D" and key2 == "U":
                    d1 = y1 - y2
                    if x1 == x2 and d1 > 0 and d1 %2 == 0:
                        cur_time = d1 // 2
                elif key1 == "L" and key2 == "R":
                    d1 = x1 - x2
                    if y1 == y2 and d1 > 0 and d1 %2 == 0:
                        cur_time = d1 // 2
                elif key1 == "L" and key2 == "U":
                    d1 = x1-x2
                    d2 = y1-y2
                    if d1 > 0 and d2 > 0 and d1 == d2:
                        cur_time = d1
                elif key1 == "R" and key2 == "U":
                    d1 = x2 - x1
                    d2 = y1 - y2
                    if d1 > 0 and d2 > 0 and d1 == d2:
                        cur_time = d1

                if cur_time is not None:
                    if out is None:
                        out = cur_time
                    else:
                        out = min(out, cur_time)


if out is None:
    print("SAFE")
else:
    print(out)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
up = []
dow = []
ri = []
le = []
m = float('inf')
for i in range(n):
    x,y,u = input().split()
    x,y = int(x),int(y)
    if u == "U":
        for cx,cy in le:
            if cx>x and cy>y:
                if cx-x == cy-y:
                    m = min(m,(cx-x)*10)
        for cx,cy in ri:
            if cx<x and cy>y:
                if x-cx == cy-y:
                    m = min(m,(x-cx)*10)
        for cx,cy in dow:
            if cx == x and cy>y:
                m = min(m,(cy-y)*5)
        up.append([x,y])
    elif u == "D":
        for cx,cy in le:
            if cx>x and cy<y:
                if cx-x == y-cy:
                    m = min(m,(cx-x)*10)
        for cx,cy in ri:
            if cx<x and cy<y:
                if x-cx == y-cy:
                    m = min(m,(x-cx)*10)
        for cx,cy in up:
            if cx == x and cy<y:
                m = min(m,(y-cy)*5)
        dow.append([x,y])
    elif u == "L":
        for cx,cy in up:
            if cx<x and cy<y:
                if cx-x == cy-y:
                    m = min(m,(x-cx)*10)
        for cx,cy in dow:
            if cx<x and cy>y:
                if x-cx == cy-y:
                    m = min(m,(x-cx)*10)
        for cx,cy in ri:
            if cy == y and cx<x:
                m = min(m,(x-cx)*5)
        le.append([x,y])
    else:
        for cx,cy in up:
            if cx>x and cy<y:
                if x-cx == cy-y:
                    m = min(m,(cx-x)*10)
        for cx,cy in dow:
            if cx>x and cy>y:
                if x-cx == y-cy:
                    m = min(m,(cx-x)*10)
        for cx,cy in le:
            if cy == y and cx>x:
                m = min(m,(cx-x)*5)
        ri.append([x,y])
if m == float('inf'):
    print("SAFE")
else:
    print(m)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

from collections import defaultdict

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

forward_diag = defaultdict(list)
backward_diag = defaultdict(list)
updown = defaultdict(list)
leftright = defaultdict(list)

N = int(input())
for _ in range(N):
    x, y, U = input().split(' ')
    x = int(x)
    y = int(y)
    U

    forward_diag[x-y] += [(x, U)]
    backward_diag[x+y] += [(x, U)]
    updown[x] += [(y, U)]
    leftright[y] += [(x, U)]

min_collisions = float("inf")

def search(lst, A, B):
    ret = float("inf")
    lst = sorted([(a, d) for (a, d) in lst if d in A+B])
    i = 0
    while i < len(lst):
        while i < len(lst) and lst[i][1] != A:
            i += 1
        j = i
        while j < len(lst) and lst[j][1] != B:
            j += 1
        if i < len(lst) and j < len(lst):
            ret = min(ret, lst[j][0]-lst[i][0])
        i += 1
    return ret

for lst in updown.values():
    min_collisions = min(min_collisions, 5*search(lst, 'U', 'D'))
for lst in leftright.values():
    min_collisions = min(min_collisions, 5*search(lst, 'R', 'L'))
for lst in forward_diag.values():
    min_collisions = min(min_collisions, 10*search(lst, 'U', 'L'))
    min_collisions = min(min_collisions, 10*search(lst, 'R', 'D'))
for lst in backward_diag.values():
    min_collisions = min(min_collisions, 10*search(lst, 'R', 'U'))
    min_collisions = min(min_collisions, 10*search(lst, 'D', 'L'))

if min_collisions == float("inf"):
    print("SAFE")
else:
    print(min_collisions)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict
N=int(input())
D=[[] for i in range(2*10**5+1)]
U=[[] for i in range(2*10**5+1)]
L=[[] for i in range(2*10**5+1)]
R=[[] for i in range(2*10**5+1)]
arr=[]


T=[[[] for i in range(2*10**5+1)] for i in range(4)]
li=['U','L','D','R']
for i in range(N):
    X,Y,v=input().split()
    X,Y=int(X),int(Y)
    arr.append((X,Y,v))
    if v=='U':
        U[X].append(Y)
    if v=='D':
        D[X].append(Y)
    if v=='L':
        L[Y].append(X)
    if v=='R':
        R[Y].append(X)
ans=float('inf')
for i in range(2*10**5+1):
    D[i].sort()
    for u in U[i]:
        b=bisect_left(D[i],u)
        if b==len(D[i]):
            continue
        ans=min(ans,5*(D[i][b]-u))
    L[i].sort()
    for r in R[i]:
        b=bisect_left(L[i],r)
        if b==len(L[i]):
            continue
        ans=min(ans,5*(L[i][b]-r))
        
def check(R,U):
    res=float('inf')
    for A,B in U.items():
        B.sort()
    for xr,yr in R:
        b=bisect_left(U[xr+yr],xr)
        if b==len(U[xr+yr]):
            continue
        res=min(res,10*(U[xr+yr][b]-xr))
    return res

def f1(x,y):return x,y
def f2(x,y):return -y,x
def f3(x,y):return -x,-y
def f4(x,y):return y,-x
fanc=[f1,f2,f3,f4]
for t in range(4):
    arr2=[]
    for x,y,v in arr:
        a,b=fanc[t](x,y)
        c=li[(li.index(v)+t)%4]
        arr2.append((a,b,c))
    r2,u2=[],defaultdict(list)
    for x,y,v in arr2:
        if v=='R':
            r2.append((x,y))
        if v=='U':
            u2[x+y].append(x)
    ans=min(ans,check(r2,u2))
print(ans if ans!=float('inf') else 'SAFE')

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict
N=int(input())
D=[[] for i in range(2*10**5+1)]
U=[[] for i in range(2*10**5+1)]
L=[[] for i in range(2*10**5+1)]
R=[[] for i in range(2*10**5+1)]
arr=[]

for i in range(N):
    X,Y,v=input().split()
    X,Y=int(X),int(Y)
    arr.append((X,Y,v))
    if v=='U':
        U[X].append(Y)
    if v=='D':
        D[X].append(Y)
    if v=='L':
        L[Y].append(X)
    if v=='R':
        R[Y].append(X)
ans=float('inf')
for i in range(2*10**5+1):
    D[i].sort()
    for u in U[i]:
        b=bisect_left(D[i],u)
        if b==len(D[i]):
            continue
        ans=min(ans,5*(D[i][b]-u))
        
    L[i].sort()
    for r in R[i]:
        b=bisect_left(L[i],r)
        if b==len(L[i]):
            continue
        ans=min(ans,5*(L[i][b]-r))
        
def check(R,U):
    res=float('inf')
    for A,B in U.items():
        B.sort()
    for xr,yr in R:
        b=bisect_left(U[xr+yr],xr)
        if b==len(U[xr+yr]):
            continue
        res=min(res,10*(U[xr+yr][b]-xr))
    return res

for t in range(4):
    r2,u2=[],defaultdict(list)
    for x,y,v in arr:
        if v=='U':
            if t==0:
                u2[x+y].append(x)
            if t==3:
                r2.append((y,-x))
        if v=='D':
            if t==2:
                u2[-y-x].append(-x)
            if t==1:
                r2.append((-y,x))
        if v=='R':
            if t==0:
                r2.append((x,y))
            if t==1:
                u2[x-y].append(-y)
        if v=='L':
            if t==2:
                r2.append((-x,-y))
            if t==3:
                u2[y-x].append(y)
    ans=min(ans,check(r2,u2))
print(ans if ans!=float('inf') else 'SAFE')

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""

上下 or 左右　それぞれの組はすぐ求まる．
同じライン上で上むきと下向きをまとめておいて，上向のaに対して，それよりも上にいて最も近い下向きのを探せば良い．
実際にはもっと早くできそうだけど二分探索で十分早いか

右+上　が当たる場合を考える．
u，rがそれぞれ約N個あるとして
uの中で一番左にあるやつ vs r全部
を考えて，uを左から順に見ていく？
微妙．

当たるとはdx=dyのこと
これ，右向きのやつを通る傾き-1の直線上（かつy座標が上の位置）に右向きのものがあれば当たれる．
45度回転させるか
X=x-y
Y=x+y
で反時計45度回転か．

uとrで，Y座標が同じで，rの方がX座標が小さい
dとlで，Y座標が同じで，dの方がX座標が小さい
dとrで，X座標が同じで，rの方がY座標が小さい
uとlで，X座標が同じで，uの方がY座標が小さい

だるすぎる，直線上の点をみよう，y=-x+kとすればx+y=kなので，kで場合わけ
各kでx座標が小さい順に並べておき，
u,rで，rの方がx座標が小さい
d,rで，rの方がx座標が小さい
u,lで，uの方がx座標が小さい
d,lで，dの方がx座標が小さい

"""
def main():
    import bisect
    
    mod=10**9+7
    N=I()
    M=200000 + 3
    inf = 10**10
    
    X=[0]*N
    Y=[0]*N
    U=[0]*N
    for i in range(N):
        xyu=input().split()
        X[i]=int(xyu[0])
        Y[i]=int(xyu[1])
        U[i]=xyu[2]
        
    # 同じ行/列のものを調べる
    
    # xu=[[-inf, inf]for _ in range(M)]
    xd=[[-inf, inf]for _ in range(M)]
    yl=[[-inf, inf]for _ in range(M)]
    # yr=[[-inf, inf]for _ in range(M)]
    
    for i in range(N):
        x=X[i]
        y=Y[i]
        if U[i] == "U":
            # xu[x].append(y)
            pass
        elif U[i] == "D":
            xd[x].append(y)
        elif U[i] == "L":
            yl[y].append(x)
        else:
            # yr[y].append(x)
            pass
    
    for i in range(M):
        # xu[i].sort()
        xd[i].sort()
        yl[i].sort()
        # yr[i].sort()
     
    ans_d=inf
    
    # uとかdで走査しても良いけど，全ての頂点を走査したいので此の形が楽
    for i in range(N):
        x=X[i]
        y=Y[i]
        u=U[i]
        
        if u=="U":
            num=bisect.bisect_left(xd[x], y)
            ne=xd[x][num]
            diff=ne-y
            ans_d=min(ans_d,diff)
            
        if u=="R":
            num=bisect.bisect_left(yl[y], x)
            ne=yl[y][num]
            diff=ne-x
            ans_d=min(ans_d,diff)
            
        """
        if u=="D":
            num=bisect.bisect_left(xu[x], y)
            pre=xu[x][num-1]
            diff=y-pre
            ans_d=min(ans_d,diff)

        if u=="L":
            num=bisect.bisect_left(yr[y], x)
            pre=yr[y][num-1]
            diff=x-pre
            ans_d=min(ans_d,diff)
        """
            
        # print(i,x,y,diff,ans_d)
    
    ################################################################        
    # ここから斜め

    ku=[[-inf, inf]for _ in range(M*2)]
    kd=[[-inf, inf]for _ in range(M*2)]
    kl=[[-inf, inf]for _ in range(M*2)]
    kr=[[-inf, inf]for _ in range(M*2)]  
    
    
    # y=x+k2のパターンもあるじゃん，k2=y-xなので適当に下駄を履かせる
    k2u=[[-inf, inf]for _ in range(M*2)]
    k2d=[[-inf, inf]for _ in range(M*2)]
    k2l=[[-inf, inf]for _ in range(M*2)]
    k2r=[[-inf, inf]for _ in range(M*2)]     

    for i in range(N):
        x=X[i]
        y=Y[i]
        k=x+y
        k2=y-x+M
        if U[i] == "U":
            ku[k].append(x)
            k2u[k2].append(x)
        elif U[i] == "D":
            kd[k].append(x)
            k2d[k2].append(x)
        elif U[i] == "L":
            kl[k].append(x)
            k2l[k2].append(x)
        else:
            kr[k].append(x)
            k2r[k2].append(x)
            
    for i in range(M*2):
        ku[i].sort()
        kd[i].sort()
        kl[i].sort()
        kr[i].sort()
        k2u[i].sort()
        k2d[i].sort()
        k2l[i].sort()
        k2r[i].sort()
       
    """     
    各kでx座標が小さい順に並べておき，
    u,rで，rの方がx座標が小さい
    d,rで，rの方がx座標が小さい
    u,lで，uの方がx座標が小さい
    d,lで，dの方がx座標が小さい
    """
    
    # print("---")    
    
    ans_d2=inf
    # uとかdで走査しても良いけど，全ての頂点を走査したいので此の形が楽
    for i in range(N):
        x=X[i]
        y=Y[i]
        k=x+y
        k2=y-x+M
        if U[i] == "U":
            num=bisect.bisect_left(kr[k],x)
            pre=kr[k][num-1]
            diff=x-pre
            ans_d2=min(ans_d2,diff)

            num=bisect.bisect_left(k2l[k2],x)
            ne=k2l[k2][num]
            diff=ne-x
            ans_d2=min(ans_d2,diff)
            
        elif U[i] == "D":
            num=bisect.bisect_left(k2r[k2],x)
            pre=k2r[k2][num-1]
            diff=x-pre
            ans_d2=min(ans_d2,diff)

            num=bisect.bisect_left(kl[k],x)
            ne=kl[k][num]
            diff=ne-x
            ans_d2=min(ans_d2,diff)
        
        # print(i,x,y,pre,ne,diff,ans_d2)
            
    
        
    ans = min(ans_d*5, ans_d2*10) #速度分で*10， ans_dは向かい合っているので/2
    
    if ans>=10**8:
        print("SAFE")
    else:
        print(ans)
        

# 本来safeではないものもsafeにしてしまっている，見落としがあるはず
        
        



        
        
            
    
            
            
        

main()

Submission status: Accepted

Solution code:
def main():
    def calc(v, w, i, j, ans):
        if v > 0:
            i[0] += 1
        elif v < 0:
            j[0] += 1
        else:
            if w > 0:
                ans[0] = min(ans[0], w)
                i[0] += 1
            else:
                j[0] += 1

    n = int(input())
    inf = 10**10
    ans = [inf]
    u_list, d_list, l_list, r_list = [], [], [], []
    for _ in range(n):
        x, y, d = input().split()
        x, y = int(x), int(y)
        if d == "D":
            d_list.append((x, y))
        elif d == "R":
            r_list.append((x, y))
        elif d == "L":
            l_list.append((x, y))
        else:
            u_list.append((x, y))
    ld, lr, ll, lu = len(d_list), len(r_list), len(l_list), len(u_list)
    # 1→u,d
    u_list.sort(key=lambda x: (x[0], x[1]))
    d_list.sort(key=lambda x: (x[0], x[1]))
    i, j = [0], [0]
    while(i[0] < lu and j[0] < ld):
        x, y = u_list[i[0]]
        p, q = d_list[j[0]]
        v = p-x
        w = (q-y)*5
        calc(v, w, i, j, ans)
    # 2→r,l
    r_list.sort(key=lambda x: (x[1], x[0]))
    l_list.sort(key=lambda x: (x[1], x[0]))
    i, j = [0], [0]
    while(i[0] < lr and j[0] < ll):
        x, y = r_list[i[0]]
        p, q = l_list[j[0]]
        v = q-y
        w = (p-x)*5
        calc(v, w, i, j, ans)
    # 3→u,l
    u_list.sort(key=lambda x: (x[0]-x[1], x[0]))
    l_list.sort(key=lambda x: (x[0]-x[1], x[0]))
    i, j = [0], [0]
    while(i[0] < lu and j[0] < ll):
        x, y = u_list[i[0]]
        p, q = l_list[j[0]]
        v = (p-q)-(x-y)
        w = (p-x)*10
        calc(v, w, i, j, ans)
    # 4→d,l
    d_list.sort(key=lambda x: (x[0]+x[1], x[0]))
    l_list.sort(key=lambda x: (x[0]+x[1], x[0]))
    i, j = [0], [0]
    while(i[0] < ld and j[0] < ll):
        x, y = d_list[i[0]]
        p, q = l_list[j[0]]
        v = (p+q)-(x+y)
        w = (p-x)*10
        calc(v, w, i, j, ans)
    # 5→u,r
    u_list.sort(key=lambda x: (x[0]+x[1], -x[0]))
    r_list.sort(key=lambda x: (x[0]+x[1], -x[0]))
    i, j = [0], [0]
    while(i[0] < lu and j[0] < lr):
        x, y = u_list[i[0]]
        p, q = r_list[j[0]]
        v = (p+q)-(x+y)
        w = (x-p)*10
        calc(v, w, i, j, ans)
    # 6→d,r
    d_list.sort(key=lambda x: (x[0]-x[1], -x[0]))
    r_list.sort(key=lambda x: (x[0]-x[1], -x[0]))
    i, j = [0], [0]
    while(i[0] < ld and j[0] < lr):
        x, y = d_list[i[0]]
        p, q = r_list[j[0]]
        v = (p-q)-(x-y)
        w = (x-p)*10
        calc(v, w, i, j, ans)
    if ans == [inf]:
        print("SAFE")
    else:
        print(ans[0])


main()

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


    diff = float("inf")

    for i in range(4):
        if i <= 1:  # do when we rotate matrix by 0, 90 degree
            ret = checkSafety_UD(XYU_list)
            diff = min(diff, ret)
        
        # do when we rotate matrix by 0, 90, 180, 270 degree
        ret = checkSafety_UR(XYU_list)
        diff = min(diff, ret)

        rotate(XYU_list)


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


def rotate(XYU_list :list):
    for i in range(len(XYU_list)):
        x,y,u = XYU_list[i][0], XYU_list[i][1], XYU_list[i][2]
        
        x2 = -y
        y2 = x
        
        if u == "U":  u2 = "L"
        if u == "D":  u2 = "R"
        if u == "L":  u2 = "D"
        if u == "R":  u2 = "U"
        
        XYU_list[i] = [x2,y2,u2]


def checkSafety_UD(XYU_list :list) -> int:
    check_UD = {}

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

    for key in check_UD:
        check_UD[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 )

    return diff_min


def checkSafety_UR(XYU_list) -> int:
    check_UR = {}

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

    for key in check_UR:
        check_UR[key].sort()


    diff_min = float("inf")
    
    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]) )

    return diff_min


if __name__ == "__main__":
    main()

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


    diff = float("inf")

    # check(1) rotate 0 degree
    ret = checkSafety_UD(XYU_list)
    diff = min(diff, ret)
    
    ret = checkSafety_UR(XYU_list)
    diff = min(diff, ret)
    
    # check(2) rotate 90 degree
    rotate(XYU_list)

    ret = checkSafety_UD(XYU_list)
    diff = min(diff, ret)
    
    ret = checkSafety_UR(XYU_list)
    diff = min(diff, ret)

    # check(3) rotate 180 degree
    rotate(XYU_list)

    ret = checkSafety_UR(XYU_list)
    diff = min(diff, ret)

    # check(4) rotate 270 degree
    rotate(XYU_list)

    ret = checkSafety_UR(XYU_list)
    diff = min(diff, ret)


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


def rotate(XYU_list :list):
    for i in range(len(XYU_list)):
        x,y,u = XYU_list[i][0], XYU_list[i][1], XYU_list[i][2]
        
        x2 = -y
        y2 = x
        
        if u == "U":  u2 = "L"
        if u == "D":  u2 = "R"
        if u == "L":  u2 = "D"
        if u == "R":  u2 = "U"
        
        XYU_list[i] = [x2,y2,u2]


def checkSafety_UD(XYU_list :list) -> int:
    check_UD = {}

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

    for key in check_UD:
        check_UD[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 )

    return diff_min


def checkSafety_UR(XYU_list) -> int:
    check_UR = {}

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

    for key in check_UR:
        check_UR[key].sort()


    diff_min = float("inf")
    
    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]) )

    return diff_min


if __name__ == "__main__":
    main()