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:
N = int(input())
PU = []
PR = []
PD = []
PL = []
P = {'U':PU, 'R':PR, 'D':PD, 'L':PL}
for _ in range(N):
    X, Y, U = input().split()
    P[U].append((int(X), int(Y)))

ans = 100000000
    
# ===== 1 =====
DU = {}
for x, y in PU:
    if x not in DU: DU[x] = []
    DU[x].append(y)

DD = {}
for x, y in PD:
    if x not in DD: DD[x] = []
    DD[x].append(y)

for x, p1 in DU.items():
    if x not in DD: continue
    p2 = DD[x]
    
    p1.sort()
    p2.sort()
    n = len(p2)
    i = 0
    for z in p1:
        while i<n and p2[i]<=z: i+=1
        if i==n: break
        ans = min(ans, (p2[i]-z)*5)

# ===== 2 =====
DR = {}
for x, y in PR:
    if y not in DR: DR[y] = []
    DR[y].append(x)

DL = {}
for x, y in PL:
    if y not in DL: DL[y] = []
    DL[y].append(x)

for y, p1 in DR.items():
    if y not in DL: continue
    p2 = DL[y]

    p1.sort()
    p2.sort()
    n = len(p2)
    i = 0
    for z in p1:
        while i<n and p2[i]<=z: i+=1
        if i==n: break
        ans = min(ans, (p2[i]-z)*5)

# ===== 3-1 =====
DR = {}
for x, y in PR:
    if x+y not in DR: DR[x+y] = []
    DR[x+y].append(x)

DU = {}
for x, y in PU:
    if x+y not in DU: DU[x+y] = []
    DU[x+y].append(x)

for key, p1 in DR.items():
    if key not in DU: continue
    p2 = DU[key]

    p1.sort()
    p2.sort()
    n = len(p2)
    i = 0
    for z in p1:
        while i<n and p2[i]<=z: i+=1
        if i==n: break
        ans = min(ans, (p2[i]-z)*10)

# ===== 3-2 =====
DD = {}
for x, y in PD:
    if x+y not in DD: DD[x+y] = []
    DD[x+y].append(x)

DL = {}
for x, y in PL:
    if x+y not in DL: DL[x+y] = []
    DL[x+y].append(x)

for key, p1 in DD.items():
    if key not in DL: continue
    p2 = DL[key]

    p1.sort()
    p2.sort()
    n = len(p2)
    i = 0
    for z in p1:
        while i<n and p2[i]<=z: i+=1
        if i==n: break
        ans = min(ans, (p2[i]-z)*10)

# ===== 4-1 =====
DR = {}
for x, y in PR:
    if x-y not in DR: DR[x-y] = []
    DR[x-y].append(x)

DD = {}
for x, y in PD:
    if x-y not in DD: DD[x-y] = []
    DD[x-y].append(x)

for key, p1 in DR.items():
    if key not in DD: continue
    p2 = DD[key]

    p1.sort()
    p2.sort()
    n = len(p2)
    i = 0
    for z in p1:
        while i<n and p2[i]<=z: i+=1
        if i==n: break
        ans = min(ans, (p2[i]-z)*10)

# ===== 4-2 =====
DU = {}
for x, y in PU:
    if x-y not in DU: DU[x-y] = []
    DU[x-y].append(x)

DL = {}
for x, y in PL:
    if x-y not in DL: DL[x-y] = []
    DL[x-y].append(x)

for key, p1 in DU.items():
    if key not in DL: continue
    p2 = DL[key]

    p1.sort()
    p2.sort()
    n = len(p2)
    i = 0
    for z in p1:
        while i<n and p2[i]<=z: i+=1
        if i==n: break
        ans = min(ans, (p2[i]-z)*10)
        
# ===== ans =====
print(ans if ans<100000000 else 'SAFE')

Submission status: Accepted

Solution code:
N, = map(int, input().split())
from collections import defaultdict
D = defaultdict(lambda : defaultdict(list))
D2 = defaultdict(lambda : defaultdict(list))

def Fm(d1, d2):
    alist = D[d1]
    blist = D[d2]
    R = 10**18
    for key in alist:
        if key not in blist:
            continue
        A, B = alist[key], blist[key]
        X=sorted(A+B, key=lambda x:x[0])
        for a, b in zip(X, X[1:]):
            if a[2] != b[2] and (a[2] == "R" or a[2] == "D"):
                R = min(R, 10*(b[0]-a[0]))
    return R

def Fm2(d1, d2):
    alist = D2[d1]
    blist = D2[d2]
    R = 10**18
    for key in alist:
        if key not in blist:
            continue
        A, B = alist[key], blist[key]
        X=sorted(A+B, key=lambda x:x[0])
        for a, b in zip(X, X[1:]):
            if a[2] != b[2] and (a[2] == "R" or a[2] == "U"):
                R = min(R, 10*(b[0]-a[0]))
    return R


Dx = defaultdict(list)
Dy = defaultdict(list)
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)
    D[d][x+y].append((x, y, d))
    D2[d][x-y].append((x, y, d))
    if d in {"R", "L"}:
        Dx[y].append((x, d))
    else:
        Dy[x].append((y, d))

R = 10**18
for key in Dx:
    X = sorted(Dx[key])
    for (x, d), (xx, d2) in zip(X, X[1:]):
        if d == "R" and d2 == "L":
            R = min(R, (xx-x)*5)
for key in Dy:
    X = sorted(Dy[key])
    for (x, d), (xx, d2) in zip(X, X[1:]):
        if d == "U" and d2 == "D":
            R = min(R, (xx-x)*5)

R = min(R, Fm("D", "L"))
R = min(R, Fm("U", "R"))
R = min(R, Fm2("D", "R"))
R = min(R, Fm2("U", "L"))
if R != 10**18:
    print(R)
else:
    print("SAFE")
#for key in D["R"]:
#    if key not in D["U"]:
#        continue
#    print(D["R"][key], D["U"][key])
#for key in D["D"]:
#    if key not in D["L"]:
#        continue
#    print(D["D"][key], D["L"][key])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
range = xrange
input = raw_input

inp = sys.stdin.read().split(); ii = 0

mapper = {'U':0, 'D':1, 'R':2, 'L':3}

n = int(inp[ii]); ii += 1
X = []
Y = []
D = []
for _ in range(n):
    x = int(inp[ii]); ii += 1
    y = int(inp[ii]); ii += 1
    d = mapper[inp[ii]]; ii += 1
    
    X.append(x)
    Y.append(y)
    D.append(d)

listdict = lambda: defaultdict(list)

Y0 = listdict()
Y1 = listdict() 
X2 = listdict() 
X3 = listdict() 

pos0 = listdict() 
pos1 = listdict() 
pos2 = listdict() 
pos3 = listdict() 

neg0 = listdict()
neg1 = listdict() 
neg2 = listdict()
neg3 = listdict()

Xset = set()
Yset = set()
posset = set()
negset = set()

for i in range(n):
    d = D[i]
    x = X[i]
    y = Y[i]

    pos = x+y
    neg = x-y

    Xset.add(x)
    Yset.add(y)
    posset.add(pos)
    negset.add(neg)

    if d == 0:
        Y0[x].append(y)
        pos0[pos].append(2 * x)
        neg0[neg].append(2 * x)
    elif d == 1:
        Y1[x].append(y)
        pos1[pos].append(2 * x)
        neg1[neg].append(2 * x)
    elif d == 2:
        X2[y].append(x)
        pos2[pos].append(2 * x)
        neg2[neg].append(2 * x)
    elif d == 3:
        X3[y].append(x)
        pos3[pos].append(2 * x)
        neg3[neg].append(2 * x)
    else:
        assert False

def sorter(A):
    for a in A.values():
        a.sort()

sorter(Y0)
sorter(Y1)
sorter(X2)
sorter(X3)

sorter(pos0)
sorter(pos1)
sorter(pos2)
sorter(pos3)

sorter(neg0)
sorter(neg1)
sorter(neg2)
sorter(neg3)

best = -1
def check(A0, A1):
    # searching for A0[i] < A1[j]
    global best
    i = 0
    n = len(A1)
    for a in A0:
        while i < n and a >= A1[i]:
            i += 1
        if i == n:
            break
        score = (A1[i] - a) * 5
        if best == -1 or best > score:
            best = score


#Y0 
#Y1  
#X2  
#X3  
#
#pos0  
#pos1  
#pos2  
#pos3  
#
#neg0 
#neg1  
#neg2 
#neg3 

for x in Xset:
    check(Y0[x], Y1[x])
for y in Yset:
    check(X2[y], X3[y])

for neg in negset:
    check(neg2[neg], neg1[neg])
    check(neg0[neg], neg3[neg])

for pos in posset:
    check(pos2[pos], pos0[pos])
    check(pos1[pos], pos3[pos])

print 'SAFE' if best == -1 else best

Submission status: Accepted

Solution code:
check=200000

import sys

input=sys.stdin.readline

N=int(input())
U=[]
R=[]
D=[]
L=[]
for i in range(N):
    x,y,u=input().split()
    x,y=int(x),int(y)
    if u=="U":
        U.append((x,y,u))
    elif u=="R":
        R.append((x,y,u))
    elif u=="D":
        D.append((x,y,u))
    else:
        L.append((x,y,u))

ans=10**18

#DR
DR=D+R
DR.sort()
data=[[] for i in range(2*check+1)]
for x,y,u in DR:
    t=y-x+check
    if u=="R":
        data[t].append(x)
    else:
        if data[t]:
            X=data[t][-1]
            ans=min(ans,2*x-2*X)

#DL
DL=D+L
DL.sort(reverse=True)
data=[[] for i in range(2*check+1)]
for x,y,u in DL:
    t=x+y
    if u=="L":
        data[t].append(x)
    else:
        if data[t]:
            X=data[t][-1]
            ans=min(ans,2*X-2*x)

#UR
UR=U+R
UR.sort()
data=[[] for i in range(2*check+1)]
for x,y,u in UR:
    t=x+y
    if u=="R":
        data[t].append(x)
    else:
        if data[t]:
            X=data[t][-1]
            ans=min(ans,2*x-2*X)

#UL
UL=U+L
UL.sort(reverse=True)
data=[[] for i in range(2*check+1)]
for x,y,u in UL:
    t=y-x+check
    if u=="L":
        data[t].append(x)
    else:
        if data[t]:
            X=data[t][-1]
            ans=min(ans,2*X-2*x)

#UD
UD=U+D
UD.sort(key=lambda x:x[1])
data=[[] for i in range(check+1)]
for x,y,u in UD:
    if u=="U":
        data[x].append(y)
    else:
        if data[x]:
            Y=data[x][-1]
            ans=min(ans,(y-Y))

#LR
LR=L+R
LR.sort()
data=[[] for i in range(check+1)]
for x,y,u in LR:
    if u=="R":
        data[y].append(x)
    else:
        if data[y]:
            X=data[y][-1]
            ans=min(ans,(x-X))

if ans==10**18:
    print("SAFE")
    exit()
print(int(ans*5))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
t=[[] for i in range(200001)]
y=[[] for i in range(200001)]
pl=[[] for i in range(400001)]
ml=[[] for i in range(400001)]
pr=[[] for i in range(400001)]
mr=[[] for i in range(400001)]
for i in range(N):
    X,Y,U=input().split()
    X=int(X)
    Y=int(Y)
    if U=="U":
        t[X].append((Y,1))
        pl[X-Y].append((X,1))
        mr[X+Y].append((X,0))
    elif U=="D":
        t[X].append((Y,0))
        pr[X-Y].append((X,0))
        ml[X+Y].append((X,1))
    elif U=="L":
        y[Y].append((X,0))
        pl[X-Y].append((X,0))
        ml[X+Y].append((X,0))
    else:
        y[Y].append((X,1))
        pr[X-Y].append((X,1))
        mr[X+Y].append((X,1))
a=3000000
for i in t:
    if not i:
        continue
    i.sort()
    c=-1000001
    for j in i:
        if j[1]:
            c=j[0]
        else:
            p=(j[0]-c)*5
            if p<a:
                a=p
for i in y:
    if not i:
        continue
    i.sort()
    c=-1000001
    for j in i:
        if j[1]:
            c=j[0]
        else:
            p=(j[0]-c)*5
            if p<a:
                a=p
for i in pl:
    if not i:
        continue
    i.sort()
    c=-2000001
    for j in i:
        if j[1]:
            c=j[0]
        else:
            p=(j[0]-c)*10
            if p<a:
                a=p
for i in pr:
    if not i:
        continue
    i.sort()
    c=-2000001
    for j in i:
        if j[1]:
            c=j[0]
        else:
            p=(j[0]-c)*10
            if p<a:
                a=p
for i in mr:
    if not i:
        continue
    i.sort()
    c=-2000001
    for j in i:
        if j[1]:
            c=j[0]
        else:
            p=(j[0]-c)*10
            if p<a:
                a=p
for i in ml:
    if not i:
        continue
    i.sort()
    c=-2000001
    for j in i:
        if j[1]:
            c=j[0]
        else:
            p=(j[0]-c)*10
            if p<a:
                a=p
if a==3000000:
    print("SAFE")
else:
    print(a)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
xyu = [None]*n
from collections import defaultdict
dx = defaultdict(list)
dy = defaultdict(list)
dxpy = defaultdict(list)
dxmy = defaultdict(list)
for i in range(n):
    x,y,u = input().split()
    x,y = (int(x), int(y))
    dx[x].append((y, u))
    dy[y].append((x, u))
    dxpy[x+y].append((x,u))
    dxmy[x-y].append((x,u))

def sub(maru, batu):
    ans = float("inf")
    if not maru or not batu:
        return ans
    maru.sort()
    batu.sort()
    j = -1
    for i in range(len(batu)):
        while j+1<len(maru) and maru[j+1]<=batu[i]:
            j += 1
        if j<len(maru) and -maru[j]+batu[i]>=0:
            ans = min(ans, -maru[j]+batu[i])
#         print(i,j, maru[i], batu[j])

#     for i in range(len(maru)):
#         while j+1<len(batu) and batu[j+1]<=maru[i]:
#             j += 1
#         if j<len(batu) and batu[j]-maru[i]>=0:
#             ans = min(ans, batu[j]-maru[i])
#         print(i,j, maru[i], batu[j])
    return ans
ans = float("inf")
for v in dy.values():
    maru = [item[0] for item in v if item[1]=="R"]
    batu = [item[0] for item in v if item[1]=="L"]
    ans = min(ans, sub(maru, batu)*5)
for v in dx.values():
    maru = [item[0] for item in v if item[1]=="U"]
    batu = [item[0] for item in v if item[1]=="D"]
    ans = min(ans, sub(maru, batu)*5)
for v in dxpy.values():
    maru = [item[0] for item in v if item[1]=="R"]
    batu = [item[0] for item in v if item[1]=="U"]
    ans = min(ans, sub(maru, batu)*10)
    maru = [item[0] for item in v if item[1]=="D"]
    batu = [item[0] for item in v if item[1]=="L"]
    ans = min(ans, sub(maru, batu)*10)
for v in dxmy.values():
    maru = [item[0] for item in v if item[1]=="R"]
    batu = [item[0] for item in v if item[1]=="D"]
    ans = min(ans, sub(maru, batu)*10)
    maru = [item[0] for item in v if item[1]=="U"]
    batu = [item[0] for item in v if item[1]=="L"]
    ans = min(ans, sub(maru, batu)*10)
if ans==float("inf"):
    ans = "SAFE"
print(ans)

Submission status: Accepted

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

def main():
  N = int(input()[:-1])
  X = collections.defaultdict(list)  # X
  Y = collections.defaultdict(list)  # Y
  XYp = collections.defaultdict(list) # X + Y
  XYn = collections.defaultdict(list) # X + Y
  YXp = collections.defaultdict(list) # Y - X
  YXn = collections.defaultdict(list) # Y - X
  
  for _ in range(N):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    if u in ('U', 'D'):
      X[x].append((y, u == 'U'))
    if u in ('R', 'L'):
      Y[y].append((x, u == 'R'))
    
    if u in ('U', 'R'):
      XYp[x + y].append((x - y, u == 'R'))
    if u in ('D', 'L'):
      XYn[x + y].append((x - y, u == 'D'))
      
    
    if u in ('U', 'L'):
      YXp[y - x].append((x + y, u == 'U'))
    if u in ('D', 'R'):
      YXn[y - x].append((x + y, u == 'R'))
  
  ans = 200000 * 100
  for x in [X, Y, XYp, XYn, YXp, YXn]:
    for V in x.values():
      V = sorted(V)
      
      for i in range(len(V)-1):
        if V[i][1] and not V[i+1][1]:
          ans = min(ans, V[i+1][0] - V[i][0])
  if ans == 200000 * 100:
    print('SAFE')
  else:
    print(ans * 5)
   
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    p = [input().split() for _ in range(n)]
    dr = defaultdict(lambda : [])
    dl = defaultdict(lambda : [])
    du = defaultdict(lambda : [])
    dd = defaultdict(lambda : [])
    ans = float("inf")
    for i in range(n):
        p[i][0] = int(p[i][0])
        p[i][1] = int(p[i][1])
        x,y,d = p[i]
        if d == "L":
            dl[y].append(x)
        elif d == "R":
            dr[y].append(x)
        elif d == "U":
            du[x].append(y)
        else:
            dd[x].append(y)
    for x in dl.keys():
        dl[x].sort()
    for x in dr.keys():
        dr[x].sort()
    for x in du.keys():
        du[x].sort()
    for x in dd.keys():
        dd[x].sort()
    for x,y,d in p:
        if d == "L":
            if dr[y]:
                i = bisect.bisect_left(dr[y],x)-1
                if i >= 0:
                    s = x-dr[y][i]
                    if s < ans:
                        ans = s
        elif d == "R":
            if dl[y]:
                i = bisect.bisect_right(dl[y],x)
                if i < len(dl[y]):
                    s = dl[y][i]-x
                    if s < ans:
                        ans = s
        elif d == "D":
            if du[x]:
                i = bisect.bisect_left(du[x],y)-1
                if i >= 0:
                    s = y-du[x][i]
                    if s < ans:
                        ans = s
        else:
            if dd[x]:
                i = bisect.bisect_right(dd[x],y)
                if i < len(dd[x]):
                    s = dd[x][i]-y
                    if s < ans:
                        ans = s
    dux = defaultdict(lambda : [])
    ddx = defaultdict(lambda : [])
    duy = defaultdict(lambda : [])
    ddy = defaultdict(lambda : [])
    for i,(a,b,d) in enumerate(p):
        x = a-b
        y = a+b
        p[i][0] = x
        p[i][1] = y
        if d == "U":
            dux[y].append(x)
            duy[x].append(y)
        elif d == "D":
            ddx[y].append(x)
            ddy[x].append(y)
    for x in dux.keys():
        dux[x].sort()
    for x in ddx.keys():
        ddx[x].sort()
    for x in duy.keys():
        duy[x].sort()
    for x in ddy.keys():
        ddy[x].sort()
    for x,y,d in p:
        if d == "L":
            if ddx[y]:
                i = bisect.bisect_left(ddx[y],x)-1
                if i >= 0:
                    s = x-ddx[y][i]
                    if s < ans:
                        ans = s
            if duy[x]:
                i = bisect.bisect_left(duy[x],y)-1
                if i >= 0:
                    s = y-duy[x][i]
                    if s < ans:
                        ans = s
        elif d == "R":
            if dux[y]:
                i = bisect.bisect_right(dux[y],x)
                if i < len(dux[y]):
                    s = dux[y][i]-x
                    if s < ans:
                        ans = s
            if ddy[x]:
                i = bisect.bisect_right(ddy[x],y)
                if i < len(ddy[x]):
                    s = ddy[x][i]-y
                    if s < ans:
                        ans = s
    if ans == float("inf"):
        print("SAFE")
    else:
        print(ans*5)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8[:], i8[:], i8[:]), cache=True)
def f(X1, Y1, X2, Y2):
    # x1,y1 から y が増える側に移動 vs x2,y2 から y が減る側に移動
    ret = 10**18
    key1 = (X1 << 32) + Y1
    key2 = (X2 << 32) + Y2
    ind = key1.argsort()
    X1, Y1, key1 = X1[ind], Y1[ind], key1[ind]
    ind = key2.argsort()
    X2, Y2, key2 = X2[ind], Y2[ind], key2[ind]
    js = np.searchsorted(key2, key1)
    for i in range(len(key1)):
        j = js[i]
        if j == len(key2):
            continue
        if X1[i] != X2[j]:
            continue
        ret = min(ret, Y2[j] - Y1[i])
    return ret

N = int(readline())
X = []
Y = []
U = []
for _ in range(N):
    x, y, u = readline().split()
    X.append(int(x))
    Y.append(int(y))
    U.append(u)

X = np.array(X, np.int64)
Y = np.array(Y, np.int64)
U = np.array(U, 'S1')

i_u = U == b'U'
i_r = U == b'R'
i_d = U == b'D'
i_l = U == b'L'

Xu, Yu = X[i_u], Y[i_u]
Xr, Yr = X[i_r], Y[i_r]
Xd, Yd = X[i_d], Y[i_d]
Xl, Yl = X[i_l], Y[i_l]

INF = 10**18
ans = INF
ans = min(ans, f(Xu, Yu, Xd, Yd))  # 上、下
ans = min(ans, f(Yr, Xr, Yl, Xl))  # 右、左
ans = min(ans, f(Xr + Yr, Xr - Yr, Xu + Yu, Xu - Yu))  # 右、上
ans = min(ans, f(Xu - Yu, Xu + Yu, Xl - Yl, Xl + Yl))  # 上、左
ans = min(ans, f(Xr - Yr, Xr + Yr, Xd - Yd, Xd + Yd))  # 右、下
ans = min(ans, f(Xd + Yd, Xd - Yd, Xl + Yl, Xl - Yl))  # 下、左
print('SAFE' if ans == INF else 5 * ans)

Submission status: Runtime Error

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: Runtime Error

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[k].append(x)
        elif U[i] == "D":
            kd[k].append(x)
            k2d[k].append(x)
        elif U[i] == "L":
            kl[k].append(x)
            k2l[k].append(x)
        else:
            kr[k].append(x)
            k2r[k].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[k],x)
            ne=k2l[k2][num]
            diff=ne-x
            ans_d2=min(ans_d2,diff)
            
        elif U[i] == "D":
            num=bisect.bisect_left(k2r[k],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()