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: Wrong Answer

Solution code:
import sys
from operator import itemgetter
L, U, R, D = [], [], [], []
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def sm(x):
    return x[0]+x[1]


def df(x):
    return x[0]-x[1]


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

Rsum = sorted(R, key=lambda x: x[0]+x[1])
Rdif = sorted(R, key=lambda x: x[0]-x[1])
R = sorted(R, key=itemgetter(1))
Lsum = sorted(L, key=lambda x: x[0]+x[1])
Ldif = sorted(L, key=lambda x: x[0]-x[1])
L = sorted(L, key=itemgetter(1))
Usum = sorted(U, key=lambda x: x[0]+x[1])
Udif = sorted(U, key=lambda x: x[0]-x[1])
U = sorted(U)
Dsum = sorted(D, key=lambda x: x[0]+x[1])
Ddif = sorted(D, key=lambda x: x[0]-x[1])
D = sorted(D)


inf = 10**18
ans = inf
# RvsU
if R and U:
    i = 0
    for u in Usum:
        ux = sm(u)
        while ux != sm(Rsum[i]):
            if i < len(Rsum) - 1 and ux <= sm(Rsum[i + 1]):
                i += 1
            else:
                break
        if ux == sm(Rsum[i]) and u[0] > Rsum[i][0]:
            ans = min(ans, u[0] - Rsum[i][0])

# RvsD
if D and R:
    i = 0
    for d in Ddif:
        dx = df(d)
        while dx != df(Rdif[i]):
            if i < len(Rdif) - 1 and dx <= df(Rdif[i + 1]):
                i += 1
            else:
                break
        if dx == df(Rdif[i]) and d[0] > Rdif[i][0]:
            ans = min(ans, d[0] - Rdif[i][0])

# LvsU
if U and L:
    i = 0
    for u in Udif:
        ux = df(u)
        while ux != df(Ldif[i]):
            if i < len(Ldif) - 1 and ux <= df(Ldif[i + 1]):
                i += 1
            else:
                break
        if ux == df(Ldif[i]) and u[0] < Ldif[i][0]:
            ans = min(ans, Ldif[i][0]-u[0])

# LvsD
if L and D:
    i = 0
    for d in Dsum:
        dx = sm(d)
        while dx != sm(Lsum[i]):
            if i < len(Lsum) - 1 and dx <= sm(Lsum[i + 1]):
                i += 1
            else:
                break
        if dx == sm(Lsum[i]) and d[0] < Lsum[i][0]:
            ans = min(ans, Lsum[i][0] - d[0])

# RvsL
if R and L:
    i = 0
    for xr, yr in R:
        while yr != L[i][1]:
            if i < len(L) - 1 and yr <= L[i + 1][1]:
                i += 1
            else:
                break
        if yr == L[i][1] and xr < L[i][0]:
            ans = min(ans, (L[i][0] - xr) // 2)

# UvsD
if U and D:
    i = 0
    for xu, yu in U:
        while xu != D[i][0]:
            if i < len(D) - 1 and xu <= D[i + 1][0]:
                i += 1
            else:
                break
        if xu == D[i][0] and yu < D[i][1]:
            ans = min(ans, (D[i][1] - yu) // 2)


if ans >= inf:
    print("SAFE")
else:
    print(ans*10)

Submission status: Wrong Answer

Solution code:
n=int(input())

from collections import defaultdict

ux=set([])
uy=defaultdict(list)

dx=set([])
dy=defaultdict(list)

ry=set([])
rx=defaultdict(list)

ly=set([])
lx=defaultdict(list)

#切片
brd=set([])
brd_dic=defaultdict(list)
blu=set([])
blu_dic=defaultdict(list)
bru=set([])
bru_dic=defaultdict(list)
bld=set([])
bld_dic=defaultdict(list)

for _ in range(n):
    x,y,u=map(str,input().split())
    x=int(x)
    y=int(y)
    if u=="U":
        ux.add(x)
        uy[x].append(y)
        blu.add(y-x)
        blu_dic[y-x].append(x)
        bru.add(y+x)
        bru_dic[y+x].append(x)

    elif u=="D":
        dx.add(x)
        dy[x].append(y)
        
        bld.add(y+x)
        bld_dic[y+x].append(x)
        brd.add(y-x)
        brd_dic[y-x].append(x)
    elif u=="R":
        ry.add(y)
        rx[y].append(x)

        bru.add(y+x)
        bru_dic[y+x].append(x)
        brd.add(y-x)
        brd_dic[y-x].append(x)

    else:
        ly.add(y)
        lx[y].append(x)
        blu.add(y-x)
        blu_dic[y-x].append(x)
        bld.add(y+x)
        bld_dic[y+x].append(x)

ans=10**12
###UDをチェック
for x in ux:
    #x座標が同じだとぶつかる可能性がある
    if x in dx:
        for uy1 in uy[x]:
            for dy1 in dy[x]:
                if uy1<dy1 and (dy1-uy1)%2==0:
                    ans=min(ans,(dy1-uy1)//2)
###RLをチェック
for y in ry:
    #x座標が同じだとぶつかる可能性がある
    if y in ly:
        for rx1 in rx[y]:
            for lx1 in lx[y]:
                if rx1<lx1 and (lx1-rx1)%2==0:
                    ans=min(ans,(lx1-rx1)//2)

#####

for b in blu:
    tmp=blu_dic[b]
    for i in range(len(tmp)-1):
        for j in range(len(tmp)):
            if abs(tmp[i]-tmp[j])%2==0 and tmp[i]!=tmp[j]:
                ans=min(ans,abs(tmp[i]-tmp[j]))


for b in bld:
    tmp=bld_dic[b]
    for i in range(len(tmp)-1):
        for j in range(len(tmp)):
            if abs(tmp[i]-tmp[j])%2==0 and tmp[i]!=tmp[j]:
                ans=min(ans,abs(tmp[i]-tmp[j]))


for b in brd:
    tmp=brd_dic[b]
    for i in range(len(tmp)-1):
        for j in range(len(tmp)):
            if abs(tmp[i]-tmp[j])%2==0 and tmp[i]!=tmp[j]:
                ans=min(ans,abs(tmp[i]-tmp[j]))


for b in bru:
    tmp=bru_dic[b]
    for i in range(len(tmp)-1):
        for j in range(len(tmp)):
            if abs(tmp[i]-tmp[j])%2==0 and tmp[i]!=tmp[j]:
                ans=min(ans,abs(tmp[i]-tmp[j]))



if ans==10**12:
    print("SAFE")
else:
    print(ans*10)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
INF = 10**9
time = INF
N = int(input())
A = [input().split(' ') for _ in range(N)]
if N == 1:
  print('SAFE')
else:
  for a, b in combinations(A, 2):
    if a[2] == b[2]:
      continue
    elif a[2] in ('U', 'D') and b[2] in ('U', 'D'):
      if a[0] == b[0]:
        time = min(abs(int(a[1]) - int(b[1])) / 2, time)
    elif a[2] in ('R', 'L') and b[2] in ('R', 'L'):
      if a[1] == b[1]:
        time = min(abs(int(a[0]) - int(b[0])) / 2, time)
    elif a[2] == 'R' and b[2] == 'D':
      if int(a[0]) < int(b[0]) and int(a[1]) < int(b[1]):
        if abs(int(a[0]) - int(b[0])) == abs(int(a[1]) - int(b[1])):
          time = min(abs(int(a[0]) - int(b[0])), time)
    elif a[2] == 'R' and b[2] == 'U':
      if int(a[0]) < int(b[0]) and int(a[1]) > int(b[1]):
        if abs(int(a[0]) - int(b[0])) == abs(int(a[1]) - int(b[1])):
          time = min(abs(int(a[0]) - int(b[0])), time)
    elif a[2] == 'L' and b[2] == 'D':
      if int(a[0]) > int(b[0]) and int(a[1]) < int(b[1]):
        if abs(int(a[0]) - int(b[0])) == abs(int(a[1]) - int(b[1])):
          time = min(abs(int(a[0]) - int(b[0])), time)
    elif a[2] == 'L' and b[2] == 'U':
      if int(a[0]) > int(b[0]) and int(a[1]) > int(b[1]):
        if abs(int(a[0]) - int(b[0])) == abs(int(a[1]) - int(b[1])):
          time = min(abs(int(a[0]) - int(b[0])), time)
    elif a[2] == 'U' and b[2] == 'R':
      if int(a[0]) > int(b[0]) and int(a[1]) < int(b[1]):
        if abs(int(a[0]) - int(b[0])) == abs(int(a[1]) - int(b[1])):
          time = min(abs(int(a[0]) - int(b[0])), time)
    elif a[2] == 'U' and b[2] == 'L':
      if int(a[0]) < int(b[0]) and int(a[1]) < int(b[1]):
        if abs(int(a[0]) - int(b[0])) == abs(int(a[1]) - int(b[1])):
          time = min(abs(int(a[0]) - int(b[0])), time)
    elif a[2] == 'D' and b[2] == 'R':
      if int(a[0]) > int(b[0]) and int(a[1]) > int(b[1]):
        if abs(int(a[0]) - int(b[0])) == abs(int(a[1]) - int(b[1])):
          time = min(abs(int(a[0]) - int(b[0])), time)
    elif a[2] == 'D' and b[2] == 'L':
      if int(a[0]) < int(b[0]) and int(a[1]) > int(b[1]):
        if abs(int(a[0]) - int(b[0])) == abs(int(a[1]) - int(b[1])):
          time = min(abs(int(a[0]) - int(b[0])), time)
  if time == INF:
    print('SAFE')
  else:
    print(time * 10 // 10)

Submission status: Wrong Answer

Solution code:
gauchex = {}
gauchey = {}
gauched = {}
gauches = {}
droitex = {}
droitey = {}
droited = {}
droites = {}
hautx = {}
hauty = {}
hautd = {}
hauts = {}

basx = {}
basy = {}
basd = {}
bass = {}
	

n=int(input())
for i in range(n):
	x,y,d = input().split()
	x = int(x)
	y = int(y)
	if d == "L":
		gauchex[x] = gauchex.get(x,[])+[[x,y]]
		gauchey[y] = gauchey.get(y,[])+[[x,y]]
		gauched[x-y] = gauched.get(x-y,[])+[[x,y]]
		gauches[x+y] = gauches.get(x+y,[])+[[x,y]]
	elif d=="R":
		droitex[x] = droitex.get(x,[])+[[x,y]]
		droitey[y] = droitey.get(y,[])+[[x,y]]
		droited[x-y] = droited.get(x-y,[])+[[x,y]]
		droites[x+y] = droites.get(x+y,[])+[[x,y]]
	elif d=="U":
		hautx[x] = hautx.get(x,[])+[[x,y]]
		hauty[y] = hauty.get(y,[])+[[x,y]]
		hautd[x-y] = hautd.get(x-y,[])+[[x,y]]
		hauts[x+y] = hauts.get(x+y,[])+[[x,y]]
	else:
		basx[x] = basx.get(x,[])+[[x,y]]
		basy[y] = basy.get(y,[])+[[x,y]]
		basd[x-y] = basd.get(x-y,[])+[[x,y]]
		bass[x+y] = bass.get(x+y,[])+[[x,y]]
	

col = []

#bas
for i in basx:
	for x,y  in basx[i]:
		for x2,y2 in droited.get(x-y,[]):
			col+= [abs(x-x2)]
		for x2,y2 in hautx.get(x,[]):
			col+=[(abs(y-y2))/2]
		for x2,y2 in gauches.get(x+y,[]):
			col+=[abs(x-x2)]
			
for i in droitex:
	for x,y in droitex[i]:
		for x2,y2 in gauchey.get(y,[]):
			col+=[(abs(x-x2))/2]
		for x2,y2 in hauts.get(x+y,[]):
			col+=[abs(x-x2)]
		
for i in hautx:
	for x,y in hautx[i]:
		for x2,y2 in gauched.get(x-y,[]):
			col+=[abs(x-x2)]
			
if col == []:print("SAFE")
else:
	# ~ print(col)
	ans = min(col)
	print(int(ans*10))

Submission status: Wrong Answer

Solution code:
#root.search(x): ◯.data == x のものが存在するある場合それを出力、ない場合Noneを出力
#root.insert(x): ◯.data == xが存在する場合Falseを出力、ない場合◯.data == x なる頂点を作る
#y.to_s(): 頂点yのdataを出力
#y.left_s(): 頂点yのleftを出力(ない場合はNone)
#root.search_lower(x,None): ○.dataがxより小さいものの中で最も大きいものを出力、ない場合Noneを出力
#root.search_higher(x,None): xより大きいものの中で最も小さいものを出力、ない場合Noneを出力

################################################################################
class Avltree:
    def __init__(self,key=None):
        self.key = key
        self.left = None
        self.right = None 
        self.balance = "Even"
    def search(self,key):
        if self.key == None:
            return None
        if self.key > key:
            if self.left == None:
                return None
            else:
                return self.left.search(key)
        if self.key < key:
            if self.right == None:
                return None
            else:
                return self.right.search(key)
        return self # self.key == keyの場合
        
    def search_lower(self,key,key_lower):
        if self.key == None:
            return key_lower
        if self.key > key:
            if self.left == None:
                return key_lower
            else:
                return self.left.search_lower(key,key_lower)
        if self.key < key:
            key_lower = self.key
            if self.right == None:
                return key_lower
            else:
                return self.right.search_lower(key,key_lower)
        #self.key == keyの場合
        if self.left == None:
            return key_lower
        else:
            if key_lower == None:
                return self.left.end_higher(self.left.key)
            else:
                return max(key_lower,self.left.end_higher(self.left.key))
    
    def search_higher(self,key,key_higher):
        if self.key == None:
            return key_higher
        if self.key > key:
            key_higher = self.key
            if self.left == None:
                return key_higher
            else:
                return self.left.search_higher(key,key_higher)
        if self.key < key:
            if self.right == None:
                return key_higher
            else:
                return self.right.search_higher(key,key_higher)
        #self.key == keyの場合
        if self.right == None:
            return key_higher
        else:
            if key_higher == None:
                return self.right.end_lower(self.right.key)
            else:
                return min(key_higher,self.right.end_lower(self.right.key))
        
    
    def end_lower(self,end_lower_key):
        if self.left == None:
            return end_lower_key
        else:
            end_lower_key = self.left.key
            return self.left.end_lower(end_lower_key)
    def end_higher(self,end_higher_key):
        if self.right == None:
            return end_higher_key
        else:
            end_higher_key = self.right.key
            return self.right.end_higher(end_higher_key)
    
            
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self,p,v): # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else :
            p.right = v 
    def insert(self,key): # rootでのみ呼ばれる挿入
        if self.key == None: # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self,key)
        elif key > self.key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self,key)
        else: # key == self.key:
            pass # do not overwrite
    def insertx(self,p,key): # replaceを呼ぶために一つ上の親を持っているinsert
        if self.key > key:
            if self.left == None:
                self.left = Avltree(key)
            else:
                if not self.left.insertx(self, key): # 左の木が生長しなければ、
                    return False # 成長しない
            if self.balance == "Right":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Left"
                return True # 成長した
            elif self.balance == "Left":
                if self.left.balance == "Right":
                    self.replace(p,self.DoubleRightRotation())
                elif self.left.balance == "Left":
                    self.replace(p,self.SingleRightRotation())
                return False # rotationを行うと成長しない
        if self.key < key:
            if self.right == None:
                self.right = Avltree(key)
            else:
                if not self.right.insertx(self, key):
                    return False 
            if self.balance == "Left":
                self.balance = "Even"
                return False
            elif self.balance == "Even":
                self.balance = "Right"
                return True
            elif self.balance == "Right":
                if self.right.balance == "Left": 
                    self.replace(p,self.DoubleLeftRotation())
                elif self.right.balance == "Right":
                    self.replace(p,self.SingleLeftRotation())
                return False
        return False # self.key == keyの時は何もしないので成長もしない 

    def to_s(self):
        return self.key
    def left_s(self):
        if self.left == None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right == None:
            return None
        return (self.right).key


n = int(input())
a = [list(input().split()) for i in range(n)]
for i in range(n):
    if a[i][2] == "R":
        a[i][2] = 1
    elif a[i][2] == "L":
        a[i][2] = 2
    elif a[i][2] == "U" :
        a[i][2] = 3
    else:
        a[i][2] = 4
    a[i][0] = int(a[i][0])
    a[i][1]=int(a[i][1])
a.sort(key=lambda x: x[2])
m = 200001
R1 = [Avltree() for i in range(400002)]
R2 = [Avltree() for i in range(400002)]
L1 = [Avltree() for i in range(400002)]
L2 = [Avltree() for i in range(400002)]
U = [Avltree() for i in range(400002)]
R = [Avltree() for i in range(400002)]

M=100000000000
for x, y, u in a:
    if u == 1:
        R1[y - x + m].insert(x)
        R2[x + y].insert(x)
        R[y].insert(x)
    elif u == 2:
        L1[x + y].insert(x)
        L2[y - x + m].insert(x)
        k = R[y].search_lower(x, None)
        if k:
            M = min((x-k)/2, M)

    if u == 3:
        k = L2[y - x + m].search_higher(x, None)
        if k:
            M = min(M, k-x)
        k = R2[x + y].search_lower(x, None)
        if k:
            M = min(M, x - k)
        U[x].insert(y)
    if u == 4:
        k = L1[x + y].search_higher(x, None)
        if k:
            M = min(M, k-x)
        k = L1[y - x + m].search_lower(x, None)
        if k:
            M = min(M, x - k)
        k = U[x].search_lower(y, None)
        if k:
            M = min(M, (y-k)/2)
print(int(10*M) if M<100000000000 else "SAFE")

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    yx_p_u = {}
    yx_p_r = {}
    yx_p_d = {}
    yx_p_l = {}

    yx_m_u = {}
    yx_m_r = {}
    yx_m_d = {}
    yx_m_l = {}

    y_d = {}
    y_u = {}
    x_r = {}
    x_l = {}

    for i in range(-200000,200000+1):
        yx_p_u[i] = []
        yx_p_r[i] = []
        yx_p_d[i] = []
        yx_p_l[i] = []

    for i in range(0,400000+1):
        yx_m_u[i] = []
        yx_m_r[i] = []
        yx_m_d[i] = []
        yx_m_l[i] = []

        if i <= 200000:
            y_d[i] = []
            y_u[i] = []
            x_r[i] = []
            x_l[i] = []


    for _ in range(n):
        x,y,u = map(str, input().split())
        x = int(x)
        y = int(y)
        yxp = y-x
        yxm = y+x
        if u == 'U':
            yx_p_u[yxp].append(x)
            yx_m_u[yxm].append(x)
            y_u[x].append(y)
        if u == 'R':
            yx_p_r[yxp].append(x)
            yx_m_r[yxm].append(x)
            x_r[y].append(x)
        if u == 'D':
            yx_p_d[yxp].append(x)
            yx_m_d[yxm].append(x)
            y_d[x].append(y)
        if u == 'L':
            yx_p_l[yxp].append(x)
            yx_m_l[yxm].append(x)
            x_l[y].append(x)


    # for i in range(-20,20+1):
    for i in range(-200000,200000+1):
        yx_p_u[i].sort()
        yx_p_r[i].sort()
        yx_p_d[i].sort()
        yx_p_l[i].sort()
        # if len(yx_p_u[i]) > 0: print(i,yx_p_u[i])
        # if len(yx_p_r[i])> 0: print(i,yx_p_r[i])
        # if len(yx_p_d[i])> 0: print(i,yx_p_d[i])
        # if len(yx_p_l[i])> 0: print(i,yx_p_l[i])


    for i in range(0,400000+1):
        yx_m_u[i].sort()
        yx_m_r[i].sort()
        yx_m_d[i].sort()
        yx_m_l[i].sort()
        if i <= 200000:
            y_d[i].sort()
            y_u[i].sort()
            x_r[i].sort()
            x_l[i].sort()
        # if yx_m_u[i]: print(i,yx_m_u)
        # if yx_m_r[i]: print(i,yx_m_u)
        # if yx_m_d[i]: print(i,yx_m_u)
        # if yx_m_l[i]: print(i,yx_m_u)


    ans = 10**9
    for i in range(-200000,200000+1):
        for v in yx_p_u[i]:
            ind = bisect_right(yx_p_l[i], v)
            ind = ind if 0 <= ind < len(yx_p_l[i]) else None
            val = yx_p_l[i][ind] if ind is not None else None
            if val is not None:
                ans = min(ans, abs(val-v)*10)

        for v in yx_p_d[i]:
            ind = bisect_left(yx_p_r[i], v) - 1
            ind = ind if 0 <= ind < len(yx_p_r[i]) else None
            val = yx_p_r[i][ind] if ind is not None else None
            if val is not None:
                ans = min(ans, abs(val-v)*10)


    for i in range(0,400000+1):
        for v in yx_m_d[i]:
            ind = bisect_right(yx_m_l[i], v)
            ind = ind if 0 <= ind < len(yx_m_l[i]) else None
            val = yx_m_l[i][ind] if ind is not None else None
            if val is not None:
                ans = min(ans, abs(val-v)*10)

        for v in yx_m_u[i]:
            ind = bisect_left(yx_m_r[i], v) - 1
            ind = ind if 0 <= ind < len(yx_m_r[i]) else None
            val = yx_m_r[i][ind] if ind is not None else None
            if val is not None:
                ans = min(ans, abs(val-v)*10)

        if i <= 200000:
            for v in y_u[i]:
                ind = bisect_right(y_d[i], v)
                ind = ind if 0 <= ind < len(y_d[i]) else None
                val = y_d[i][ind] if ind is not None else None
                if val is not None:
                    ans = min(ans, abs(val-v)*10/2)

            for v in x_r[i]:
                ind = bisect_right(x_l[i], v)
                ind = ind if 0 <= ind < len(x_l[i]) else None
                val = x_l[i][ind] if ind is not None else None
                if val is not None:
                    ans = min(ans, abs(val-v)*10/2)


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N = int(input())

PP = {
  "D" : [],
  "U" : [],
  "L" : [],
  "R" : [],
}

for i in range(N):
  x,y,d = input().split()
  x,y = int(x), int(y)
  PP[d].append((x,y,x+y, y-x))
  
#print(PP)
ans = 1e10
# DvsU
if PP["D"] and PP["U"]:
  PD = sorted(PP['D'])
  PU = sorted(PP['U'])
  j = 0
  for i in range(len(PD)):
    while j < len(PU)-1 and PD[i][0] > PU[j][0]:
      j += 1

      if PD[i][0] == PU[j][0]:
        if PD[i][1] >= PU[j][1]:
          ans = min(ans, (PD[i][1] - PU[j][1]) * 5)
  
# L vs R
if PP["L"] and PP["R"]:
  PL = sorted(PP["L"], key=itemgetter(1))
  PR = sorted(PP["R"], key=itemgetter(1))
  j = 0
  for i in range(len(PL)):
    while j < len(PR)-1 and PL[i][1] > PR[j][1]:
      j += 1

    if PL[i][1] == PR[j][1]:
      if PL[i][0] >= PR[j][0]:
         ans = min(ans, (PL[i][0] - PR[j][0]) * 5)

# D vs R
# y = x + k <-> y-x = k が同一の点は当たる可能性
if PP["D"] and PP["R"]:
  PD = sorted(PP['D'], key=itemgetter(3))
  PR = sorted(PP['R'], key=itemgetter(3))
  j = 0
  for i in range(len(PD)):
    while j < len(PR)-1 and PD[i][3] > PR[j][3]:
      j += 1
    if PD[i][3] == PR[j][3]:
      if PD[i][2] >= PR[j][2]:
         ans = min(ans, abs(PD[i][2] - PR[j][2]) * 5)

# R vs U
# y = -x + k <-> y+x = k が同一の点は当たる可能性
if PP["R"] and PP["U"]:
  PR = sorted(PP['R'], key=itemgetter(2))
  PU = sorted(PP['U'], key=itemgetter(2))
  j = 0
  for i in range(len(PR)):
    while j < len(PU)-1 and PR[i][2] > PU[j][2]:
      j += 1
    if PR[i][2] == PU[j][2]:
      if PR[i][3] >= PU[j][3]:
         ans = min(ans, abs(PR[i][3] - PU[j][3]) * 5)

# D vs R
# U vs L
# y = x + k <-> y-x = k が同一の点は当たる可能性
if PP["L"] and PP["U"]:
  PU = sorted(PP['U'], key=itemgetter(3))
  PL = sorted(PP['L'], key=itemgetter(3))
  j = 0
  for i in range(len(PU)):
    while j < len(PL)-1 and PU[i][3] > PL[j][3]:
      j += 1
    if PU[i][3] == PL[j][3]:
      if PU[i][2] <= PL[j][2]:
         ans = min(ans, abs(PU[i][2] - PL[j][2]) * 5)

# R vs U
# L vs D
# y = -x + k <-> y+x = k が同一の点は当たる可能性
if PP["D"] and PP["L"]:
  PL = sorted(PP['L'], key=itemgetter(2))
  PD = sorted(PP['D'], key=itemgetter(2))
  j = 0
  for i in range(len(PL)):
    while j < len(PD)-1 and PL[i][2] > PD[j][2]:
      j += 1
    if PL[i][2] == PD[j][2]:
      if PL[i][3] <= PD[j][3]:
         ans = min(ans, abs(PL[i][3] - PD[j][3]) * 5)

print(ans if ans < 1e10 else "SAFE")

Submission status: Wrong Answer

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

up_slopes = [[] for _ in range(400005)]
down_slopes = [[] for _ in range(400005)]
xs = [[] for _ in range(200005)]
ys = [[] for _ in range(200005)]



for XYU in XYUs:
    #y切片
    up_slopes[int(XYU[1])-int(XYU[0])+200000].append([int(XYU[0]),XYU[2]])
    down_slopes[int(XYU[1])+int(XYU[0])].append([int(XYU[0]),XYU[2]])
    xs[int(XYU[0])].append([int(XYU[1]),XYU[2]])
    ys[int(XYU[1])].append([int(XYU[0]),XYU[2]])
    
min_val = int(1e+100)
for up_slope in up_slopes:
    U_posi = -1
    R_posi = -1
    incidents = copy.deepcopy(up_slope)
    incidents = sorted(incidents)
    for incident in up_slope:
        if incident[1] == "U":
            U_posi = incident[0]
        elif incident[1] == "R":
            R_posi = incident[0]
        elif incident[1] == "D" and R_posi != -1:
            accident = incident[0]-R_posi
            if min_val > accident:
                min_val = accident
        elif incident[1] == "L" and U_posi != -1:
            accident = incident[0]-U_posi
            if min_val > 10*accident:
                min_val = accident

for down_slope in down_slopes:
    D_posi = -1
    R_posi = -1
    incidents = copy.deepcopy(down_slope)
    incidents = sorted(incidents)
    for incident in incidents:
        if incident[1] == "D":
            D_posi = incident[0]
        elif incident[1] == "R":
            R_posi = incident[0]
        elif incident[1] == "U" and R_posi != -1:
            accident = incident[0]-R_posi
            if min_val > accident:
                min_val = accident
        elif incident[1] == "L" and D_posi != -1:
            accident = incident[0]-D_posi
            if min_val > 10*accident:
                min_val = accident


for x in xs:
    U_posi = -1
    incidents = copy.deepcopy(x)
    incidents = sorted(incidents)
    for incident in incidents:
        if incident[1] == "U":
            U_posi = incident[0]
        elif incident[1] == "D" and U_posi!=-1:
            if min_val > 10*(incident[0]-U_posi)/2:
                min_val = (incident[0]-U_posi)/2
            
for y in ys:
    R_posi = -1
    incidents = copy.deepcopy(y)
    incidents = sorted(incidents)
    for incident in incidents:
        if incident[1] == "R":
            R_posi = incident[0]
        elif incident[1] == "L" and R_posi!=-1:
            if min_val > 10*(incident[0]-R_posi)//2:
                min_val = (incident[0]-R_posi)//2
if min_val < 300000:
    print(int(min_val))
else:
    print("SAFE")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

n = int(input())
# x, yの値 URDLの順
p = [[] for _ in range(4)]
# xに対するyの値 URDLの順
px = [defaultdict(list) for _ in range(4)]
# yに対するyの値 URDLの順
py = [defaultdict(list) for _ in range(4)]
# x, yの和　URDLの順
s = [defaultdict(list) for _ in range(4)]
# x, yの差　URDLの順
d = [defaultdict(list) for _ in range(4)]

directions = {"U":0, "R":1, "D":2, "L":3}

for i in range(n):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    p.append([x, y])
    px[directions[u]][x].append(y)
    py[directions[u]][y].append(x)
    s[directions[u]][x+y].append([x, y])
    d[directions[u]][x-y].append([x, y])

ans = 10**9

# R, Uパターン
keys = list(s[directions["R"]].keys())
for k in keys:
    for rx, ry in s[directions["R"]][k]:
        for ux, uy in s[directions["U"]][k]:
            if rx > ux:
                continue
            ans = min(ans, abs(rx-ux)*10)
# L, Dパターン
keys = list(s[directions["L"]].keys())
for k in keys:
    for lx, ly in s[directions["L"]][k]:
        for dx, dy in s[directions["D"]][k]:
            if lx < dx:
                continue
            ans = min(ans, abs(lx-dx)*10)
# L, Uパターン
keys = list(d[directions["L"]].keys())
for k in keys:
    for lx, ly in d[directions["L"]][k]:
        for ux, uy in d[directions["U"]][k]:
            if lx < ux:
                continue
            ans = min(ans, abs(lx-ux)*10)
# R, Dパターン
keys = list(d[directions["R"]].keys())
for k in keys:
    for rx, ry in d[directions["R"]][k]:
        for dx, dy in d[directions["D"]][k]:
            if rx > dx:
                break
            ans = min(ans, abs(rx-dx)*10)

# U, Dパターン
keys = list(px[directions["U"]].keys())
for k in keys:
    if len(px[directions["D"]][k]) == 0:
        continue
    px[directions["D"]][k].sort()
    for uy in px[directions["U"]][k]:
        if uy > px[directions["D"]][k][-1]:
            break
        pos = bisect.bisect_left(px[directions["D"]][k], uy)
        ans = min(ans, (px[directions["D"]][k][pos]-uy)*5)

# R, Lパターン
keys = list(py[directions["R"]].keys())
for k in keys:
    if len(py[directions["L"]][k]) == 0:
        continue
    py[directions["L"]][k].sort()
    for uy in py[directions["R"]][k]:
        if uy > py[directions["L"]][k][-1]:
            break
        pos = bisect.bisect_left(py[directions["L"]][k], uy)
        ans = min(ans, (py[directions["L"]][k][pos]-uy)*5)

if ans == 10**9:
    ans = "SAFE"
print(ans)