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:
x=list()
y=list()
u=list()
S=list()
N=int(input())
for i in range(N):
  X,Y,U=input().split()
  X=int(X)
  Y=int(Y)
  if U=="U":
    for i in range(i-1):
      if y[i]>Y:
        if u[i]=="R":
          if x[i]+y[i]==X+Y:
            S.append(abs(X-x[i])*10)
        elif u[i]=="D":
          if x[i]==X:
            S.append(abs(Y-y[i])*5)
        elif u[i]=="L":
          if x[i]-y[i]==X-Y:
            S.append(abs(X-x[i])*10)
  if U=="R":
    for i in range(i-1):
      if X<x[i]:
        if u[i]=="D":
          if x[i]-y[i]==X-Y:
            S.append(abs(X-x[i])*10)
        elif u[i]=="L":
          if y[i]==Y:
            S.append(abs(X-x[i])*5)
        elif u[i]=="U":
          if x[i]+y[i]==X+Y:
            S.append(abs(X-x[i])*10)
  if U=="L":
    for i in range(i-1):
      if X<x[i]:
        if u[i]=="D":
          if x[i]+y[i]==X+Y:
            S.append(abs(X-x[i])*10)
        elif u[i]=="R":
          if y[i]==Y:
            S.append(abs(X-x[i])*5)
        elif u[i]=="U":
          if x[i]-y[i]==X-Y:
            S.append(abs(X-x[i])*10)
  if U=="D":
    for i in range(i-1):
      if y[i]<Y:
        if u[i]=="R":
          if x[i]-y[i]==X-Y:
            S.append(abs(X-x[i])*10)
        elif u[i]=="L":
          if x[i]+y[i]==X+Y:
            S.append(abs(X-x[i])*10)
        elif u[i]=="U":
          if x[i]==X:
            S.append(abs(Y-y[i])*5)
  x.append(X)
  y.append(Y)
  u.append(U)
if len(S)==0:
  print("SAFE")
else:
  print(min(S))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = []
Y = []
U = []
time = 10**10
for i in range(N):
  xappend, yappend, uappend = input().split()
  xappend = int(xappend)
  yappend = int(yappend)
  X.append(xappend)
  Y.append(yappend)
  U.append(uappend)
  if i > 0:
    for j in range(i):
      if U[i] == "U" and U[j] == "D":
        if Y[i] < Y[j] and X[i] == X[j]:
          time = min((Y[j]-Y[i])*5, time)

      elif U[i] == "D" and U[j] == "U":
          if Y[i] > Y[j] and X[i] == X[j]:
            time = min((Y[i]-Y[j])*5, time)

      elif U[i] == "R" and U[j] == "L":
        if X[i] < X[j] and Y[i] == Y[j]:
          time = min((X[j]-X[i])*5, time)

      elif U[i] == "L" and U[j] == "R":
        if X[i] > X[j] and Y[i] == Y[j]:
          time = min((X[i]-X[j])*5, time)

      elif U[i] == "U" and U[j] == "R":
        if X[i] > X[j] and Y[i] < Y[j] and X[i]-X[j] == Y[j]-Y[i]:
          time = min((X[i]-X[j])*5, time)

      elif U[i] == "U" and U[j] == "L":
        if X[i] < X[j] and Y[i] < Y[j] and X[j]-X[i] == Y[j]-Y[i]:
          time = min((X[j]-X[i])*5, time)

      elif U[i] == "D" and U[j] == "R":
        if X[i] > X[j] and Y[i] > Y[j] and X[i]-X[j] == Y[i]-Y[j]:
          time = min((X[i]-X[j])*5, time)

      elif U[i] == "D" and U[j] == "L":
        if X[i] > X[j] and Y[i] < Y[j] and X[j]-X[i] == Y[j]-Y[i]:
          time = min((X[j]-X[i])*5, time)

      elif U[i] == "R" and U[j] == "U":
        if X[i] < X[j] and Y[i] > Y[j] and X[j]-X[i] == Y[i]-Y[j]:
          time = min((X[j]-X[i])*5, time)

      elif U[i] == "R" and U[j] == "D":
        if X[i] < X[j] and Y[i] > Y[j] and X[j]-X[i] == Y[j]-Y[i]:
          time = min((X[i]-X[j])*5, time)

      elif U[i] == "L" and U[j] == "U":
        if X[i] < X[j] and Y[i] > Y[j] and X[i]-X[j] == Y[i]-Y[j]:
          time = min((X[j]-X[i])*5, time)

      elif U[i] == "L" and U[j] == "D":
        if X[i] > X[j] and Y[i] < Y[j] and X[i]-X[j] == Y[j]-Y[i]:
          time = min((X[i]-X[j])*5, time)

if time < 10**8:
  print(time)
else:
  print("SAFE")

Submission status: Wrong Answer

Solution code:
import itertools
from math import ceil

def main():
    n = int(input())
    ans = 10**9
    u = []
    r = []
    d = []
    l = []
    for _ in range(n):
        k = input().split()
        x,y = int(k[0]),int(k[1])
        if(k[2] == "U"):
            u.append((x,y))
        elif(k[2] == "R"):
            r.append((x,y))
        elif(k[2] == "D"):
            d.append((x,y))
        elif(k[2] == "L"):
            l.append((x,y))

    prd = list(itertools.product(l,r))
    for j in prd:
        one = j[0]
        two = j[1]
        if(one[1] == two[1] and one[0] > two[0]):
            dif = abs(one[0] - two[0])
            if(dif % 2 == 0):
                ans = min(ans,dif//2*10)
            
    prd = list(itertools.product(u,d))
    for j in prd:
        one = j[0]
        two = j[1]
        if(one[0] == two[0] and one[1] < two[1]):
            dif = abs(one[1] - two[1])
            if(dif % 2 == 0):
                ans = min(ans,dif//2 * 10)

    prd = list(itertools.product(u,r))
    for j in prd:
        one = j[0]
        two = j[1]
        if(one[0]-two[0] == two[1]-one[1] and one[0]-two[0] > 0 and one[1] - two[1] < 0):
            ans = min(ans,(one[0]-two[0])*10)

    prd = list(itertools.product(u,l))
    for j in prd:
        one = j[0]
        two = j[1]
        if(-one[0] + two[0] == one[1] - two[1] and one[0]-two[0] < 0 and one[1] - two[1] < 0):
            ans = min(ans,(two[0]-one[0])*10)
    
    prd = list(itertools.product(d,r))
    for j in prd:
        one = j[0]
        two = j[1]
        if(one[0]-two[0] == one[1]-two[1] and one[0]-two[0] > 0 and one[1] - two[1] < 0):
            ans = min(ans,(-two[0] + one[0])*10)

    prd = list(itertools.product(d,l))
    for j in prd:
        one = j[0]
        two = j[1]
        if(two[0]-one[0] == one[1] - two[1] and one[0]-two[0] < 0 and one[1] - two[1] > 0):
            ans = min(ans,(two[0] - one[0])*10)
    if(ans == 10**9):
        print("SAFE")
        return
    else:
        print(ans)
        return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
big = 800010
sml = 400000
pp = [[[] for _ in range(big)] for _ in range(8)]
mm = [[[] for _ in range(sml//2+1)] for _ in range(4)]
for _ in range(n):
  x,y,d = input().split()
  x = int(x)
  y = int(y)
  if d == 'R':
    pp[0][+x+y].append(+y)
    pp[2][+x-y].append(-y)
    mm[0][y].append(x)
  if d == 'L':
    pp[4][-x+y].append(+y)
    pp[6][-x-y].append(-y)
    mm[1][y].append(x)
  if d == 'U':
    pp[1][+x+y].append(+x)
    pp[5][-x+y].append(-x)
    mm[2][x].append(y)
  if d == 'D':
    pp[3][+x-y].append(+x)
    pp[7][-x-y].append(-x)
    mm[3][x].append(y)
import bisect
inf = 10**10
ans = inf
def ser(lx,ly,su):
  global ans
  lly = len(ly)
  for xx in lx:
    b = bisect.bisect_left(ly,su-xx)
    if b != lly:
      ans = min(ans,(xx+ly[b]-su)*10)
    else:
      pass
for d in range(4):
  xd = 2*d
  yd = 2*d+1
  for sun in range(-sml,sml+1):
    if pp[xd][sun] and pp[yd][sun]:
      #print(pp[xd][sun],pp[yd][sun],sun,xd,yd)
      ser(pp[xd][sun],pp[yd][sun],sun)
for sun in range(0,sml//2+1):
  if mm[0][sun] and mm[1][sun]:
    llm = len(mm[1][sun])
    for xx in mm[0][sun]:
      b = bisect.bisect_left(mm[1][sun],xx)
      if b != llm:
        ans = min(ans,(mm[1][sun][b]-xx)*5)
      else:
        pass
for sun in range(0,sml//2+1):
  if mm[2][sun] and mm[3][sun]:
    llm = len(mm[3][sun])
    for yy in mm[2][sun]:
      b = bisect.bisect_left(mm[3][sun],yy)
      if b != llm:
        ans = min(ans,(mm[3][sun][b]-yy)*5)
      else:
        pass
#print(ans)
if ans == inf:
  print('SAFE')
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    xyp = [input().split() for _ in [0]*n]
    for i in range(n):
        xyp[i][0] = int(xyp[i][0])
        xyp[i][1] = int(xyp[i][1])
    inf = 10**10
    ans = inf
    u_list, d_list, l_list, r_list = [], [], [], []
    for x, y, d in xyp:
        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))
    # 1→u,d
    li, lj = len(u_list), len(d_list)
    u_list.sort()
    d_list.sort()
    i, j = 0, 0
    while(i < li and j < lj):
        v = d_list[j][0] - u_list[i][0]
        w = (d_list[j][1] - u_list[i][1])*5
        if v > 0:
            i += 1
        elif v < 0:
            j += 1
        else:
            if w > 0:
                ans = min(ans, w)
                i += 1
            else:
                j += 1
    # 2→r,l
    li, lj = len(r_list), len(l_list)
    r_list.sort(key=lambda x: x[1])
    l_list.sort(key=lambda x: x[1])
    i, j = 0, 0
    while(i < li and j < lj):
        v = l_list[j][1] - r_list[i][1]
        w = (l_list[j][0] - r_list[i][0])*5
        if v > 0:
            i += 1
        elif v < 0:
            j += 1
        else:
            if w > 0:
                ans = min(ans, w)
                i += 1
            else:
                j += 1
    # 3→u,l
    li, lj = len(u_list), len(l_list)
    u_list.sort(key=lambda x: x[0]-x[1])
    l_list.sort(key=lambda x: x[0]-x[1])
    i, j = 0, 0
    while(i < li and j < lj):
        v = l_list[j][0]-l_list[j][1] - u_list[i][0]+u_list[i][1]
        w = (l_list[j][0] - u_list[i][0])*10
        if v > 0:
            i += 1
        elif v < 0:
            j += 1
        else:
            if w > 0:
                ans = min(ans, w)
                i += 1
            else:
                j += 1
    # 4→d,l
    li, lj = len(d_list), len(l_list)
    d_list.sort(key=lambda x: x[0]+x[1])
    l_list.sort(key=lambda x: x[0]+x[1])
    i, j = 0, 0
    while(i < li and j < lj):
        v = l_list[j][0]+l_list[j][1] - d_list[i][0]-d_list[i][1]
        w = (l_list[j][0] - d_list[i][0])*10
        if v > 0:
            i += 1
        elif v < 0:
            j += 1
        else:
            if w > 0:
                ans = min(ans, w)
                i += 1
            else:
                j += 1
    # 5→u,r
    li, lj = len(u_list), len(r_list)
    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 < li and j < lj):
        v = r_list[j][0]+r_list[j][1] - u_list[i][0]-u_list[i][1]
        w = (u_list[i][0] - r_list[j][0])*10
        if v > 0:
            i += 1
        elif v < 0:
            j += 1
        else:
            if w > 0:
                ans = min(ans, w)
                i += 1
            else:
                j += 1
    # 6→d,r
    li, lj = len(d_list), len(r_list)
    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 < li and j < lj):
        v = r_list[j][0]-r_list[j][1] - d_list[i][0]+d_list[i][1]
        w = d_list[i][0] - r_list[j][0]
        if v > 0:
            i += 1
        elif v < 0:
            j += 1
        else:
            if w > 0:
                ans = min(ans, w*10)
                i += 1
            else:
                j += 1
    if ans == inf:
        print("SAFE")
    else:
        print(ans)


main()

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)

            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)


    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
INF = float("inf")

def bisect_l(L, i, target):
    ok = len(L)  # target以上
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if L[mid][i] >= target:
            ok = mid
        else:
            ng = mid
    return ok

N = int(input())
# X = [0] * N;  Y = [0] * N;  d = [0] * N;
U = [];  D = [];  R = [];  L = [];
ans = INF
for i in range(N):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    if d == 'U':
        U.append((x, y, x + y, x - y))
    elif d == 'D':
        D.append((x, y, x + y, x - y))
    elif d == 'R':
        R.append((x, y, x + y, x - y))
    else:
        L.append((x, y, x + y, x - y))
    # X[i] = int(X[i])
    # Y[i] = int(Y[i])

# UとD
U.sort()
D.sort()
# Dx = [x for (x, y) in D]
for ux, uy, xpy, xmy in U:
    # i = bisect_left(Dx, ux)
    i = bisect_l(D, 0, ux)
    # if i < len(Dx) and Dx[i] == ux:
    if i < len(D) and D[i][0] == ux:
        ans = (D[i][1] - uy) * 5

# RとL
R.sort()
L.sort()
# Lx = [x for (x, y) in L]
for rx, ry, xpy, xmy in R:
    # i = bisect_left(Lx, rx)
    i = bisect_l(L, 1, ry)
    if i < len(L) and L[i][1] == ry:
        ans = min(ans, (L[i][0] - rx) * 5)

# Us = [x + y for (x, y) in U]
# Ud = [x - y for (x, y) in U]
# Ds = [x + y for (x, y) in D]
# Dd = [x - y for (x, y) in D]
# Rs = [x + y for (x, y) in R]
# Rd = [x - y for (x, y) in R]
# Ls = [x + y for (x, y) in L]
# Ld = [x - y for (x, y) in L]


# UとR
R.sort(key = lambda x : x[2])
L.sort(key = lambda x : x[2])
for (x, y, xpy, xmy) in U:
    i = bisect_l(R, 2, xpy)
    if i < len(R) and R[i][2] == xpy:
        ans = min(ans, (R[i][1] - y) * 10)

# DとL
for (x, y, xpy, xmy) in D:
    i = bisect_l(L, 2, xpy)
    if i < len(L) and L[i][2] == xpy:
        ans = min(ans, (y - L[i][1]) * 10)

L.sort(key = lambda x : x[3])
R.sort(key = lambda x : x[3])
# UとL
for (x, y, xpy, xmy) in U:
    i = bisect_l(L, 3, xmy)
    if i < len(L) and L[i][3] == xmy:
        ans = min(ans, (L[i][0] - x) * 10)

# DとR
for (x, y, xpy, xmy) in D:
    i = bisect_l(R, 3, xmy)
    if i < len(R) and R[i][3] == xmy:
        ans = min(ans, (x - R[i][0]) * 10)

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

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((k-x)/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-M)/2)
print(int(10*M) if M<100000000000 else "SAFE")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    u_planes = []
    d_planes = []
    r_planes = []
    l_planes = []
    minsec = 999999999
    for _ in range(n):
        x, y, u = input().split()
        if u=='U': u_planes.append((int(x), int(y)))
        if u=='D': d_planes.append((int(x), int(y)))
        if u=='R': r_planes.append((int(x), int(y)))
        if u=='L': l_planes.append((int(x), int(y)))

    for x,y in u_planes:
        pp = [(y_-y)/2 for (x_,y_) in d_planes if x==x_ and y<y_]
        if len(pp)>0:
            minsec = min(min(pp), minsec)
    for x,y in r_planes:
        pp = [(x_-x)/2 for (x_,y_) in l_planes if y==y_ and x<x_]
        if len(pp)>0:
            minsec = min(min(pp), minsec)

    for x,y in u_planes:
        pp = [y_-y for (x_,y_) in r_planes if (y_-y)==(x-x_)]
        if len(pp)>0:
            minsec = min(min(pp), minsec)
        pp = [y_-y for (x_,y_) in l_planes if (y_-y)==(x_-x)]
        if len(pp)>0:
            minsec = min(min(pp), minsec)
    for x,y in d_planes:
        pp = [y-y_ for (x_,y_) in r_planes if (y-y_)==(x-x_)]
        if len(pp)>0:
            minsec = min(min(pp), minsec)
        pp = [y-y_ for (x_,y_) in l_planes if (y-y_)==(x_-x)]
        if len(pp)>0:
            minsec = min(min(pp), minsec)

    print(minsec/10)

main()

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)