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:
#十字で合流する場合
n=int(input())
ud=[[[],[]] for i in range(200001)]
rl=[[[],[]] for i in range(200001)]
from bisect import *
cross=[[dict(),dict()] for i in range(4)]
for i in range(n):
    x,y,u=input().split()
    x,y=int(x),int(y)
    if u=="U":
        ud[x][0].append(y)
        if x+y in cross[0][1]:
            cross[0][1][x+y].append(x)
        else:
            cross[0][1][x+y]=[x]
        if x-y in cross[1][1]:
            cross[1][1][x-y].append(x)
        else:
            cross[1][1][x-y]=[x]
    elif u=="D":
        ud[x][1].append(y)
        if x+y in cross[3][1]:
            cross[3][1][x+y].append(x)
        else:
            cross[3][1][x+y]=[x]
        if x-y in cross[2][1]:
            cross[2][1][x-y].append(x)
        else:
            cross[2][1][x-y]=[x]
    elif u=="R":
        rl[y][0].append(x)
        if x+y in cross[0][0]:
            cross[0][0][x+y].append(x)
        else:
            cross[0][0][x+y]=[x]
        if x-y in cross[2][0]:
            cross[2][0][x-y].append(x)
        else:
            cross[2][0][x-y]=[x]
    else:
        rl[y][1].append(x)
        if x+y in cross[3][0]:
            cross[3][0][x+y].append(x)
        else:
            cross[3][0][x+y]=[x]
        if x-y in cross[1][0]:
            cross[1][0][x-y].append(x)
        else:
            cross[1][0][x-y]=[x]
for i in range(200001):
    ud[i][0].sort()
    ud[i][1].sort()
    rl[i][0].sort()
    rl[i][1].sort()
ans1=[]
for i in range(200001):
    l1,l2=len(ud[i][0]),len(ud[i][1])
    if l1 and l2:
        for j in ud[i][0]:
            b=bisect_left(ud[i][1],j)
            if b!=l2:
                ans1.append(ud[i][1][b]-j)
    l1,l2=len(rl[i][0]),len(rl[i][1])
    if l1 and l2:
        for j in rl[i][0]:
            b=bisect_left(rl[i][1],j)
            if b!=l2:
                ans1.append(rl[i][1][b]-j)
for i in range(4):
    for j in range(2):
        for k in cross[i][j]:
            cross[i][j][k].sort()
#print(cross)
ans2=[]
for i in range(4):
    for j in cross[i][1]:
        if j in cross[i][0]:
            l=len(cross[i][0][j])
            if i%2==1:
                for k in cross[i][1][j]:
                    b=bisect_left(cross[i][0][j],k)
                if b!=l:
                    ans2.append(cross[i][0][j][b]-k)
            else:
                for k in cross[i][1][j]:
                    b=bisect_right(cross[i][0][j],k)-1
                if b!=-1:
                    ans2.append(k-cross[i][0][j][b])
if len(ans1) and len(ans2):
    print(min(min(ans1)*5,min(ans2)*10))
elif len(ans1):
    print(min(ans1)*5)
elif len(ans2):
    print(min(ans2)*10)
else:
    print("SAFE")

Submission status: Wrong Answer

Solution code:
#十字で合流する場合
n=int(input())
ud=[[[],[]] for i in range(200001)]
rl=[[[],[]] for i in range(200001)]
from bisect import *
cross=[[dict(),dict()] for i in range(4)]
for i in range(n):
    x,y,u=input().split()
    x,y=int(x),int(y)
    if u=="U":
        ud[x][0].append(y)
        if x+y in cross[0][1]:
            cross[0][1][x+y].append(x)
        else:
            cross[0][1][x+y]=[x]
        if x-y in cross[1][1]:
            cross[1][1][x-y].append(x)
        else:
            cross[1][1][x-y]=[x]
    elif u=="D":
        ud[x][1].append(y)
        if x+y in cross[3][1]:
            cross[3][1][x+y].append(x)
        else:
            cross[3][1][x+y]=[x]
        if x-y in cross[2][1]:
            cross[2][1][x-y].append(x)
        else:
            cross[2][1][x-y]=[x]
    elif u=="R":
        rl[y][0].append(x)
        if x+y in cross[0][0]:
            cross[0][0][x+y].append(x)
        else:
            cross[0][0][x+y]=[x]
        if x-y in cross[2][0]:
            cross[2][0][x-y].append(x)
        else:
            cross[2][0][x-y]=[x]
    else:
        rl[y][1].append(x)
        if x+y in cross[3][0]:
            cross[3][0][x+y].append(x)
        else:
            cross[3][0][x+y]=[x]
        if x-y in cross[1][0]:
            cross[1][0][x-y].append(x)
        else:
            cross[1][0][x-y]=[x]
for i in range(200001):
    ud[i][0].sort()
    ud[i][1].sort()
    rl[i][0].sort()
    rl[i][1].sort()
ans1=[]
for i in range(200001):
    l1,l2=len(ud[i][0]),len(ud[i][1])
    if l1 and l2:
        for j in ud[i][0]:
            b=bisect_left(ud[i][1],j)
            if b!=l2:
                ans1.append(ud[i][1][b]-j)
    l1,l2=len(rl[i][0]),len(rl[i][1])
    if l1 and l2:
        for j in rl[i][0]:
            b=bisect_left(rl[i][1],j)
            if b!=l2:
                ans1.append(rl[i][1][b]-j)
for i in range(4):
    for j in range(2):
        for k in cross[i][j]:
            cross[i][j][k].sort()
#print(cross)
ans2=[]
for i in range(4):
    for j in cross[i][1]:
        if j in cross[i][0]:
            l=len(cross[i][0][j])
            if i%2==1:
                for k in cross[i][1][j]:
                    b=bisect_left(cross[i][0][j],k)
                if b!=l:
                    ans2.append(cross[i][0][j][b]-k)
            else:
                for k in cross[i][1][j]:
                    b=bisect_right(cross[i][0][j],k)-1
                if b!=-1:
                    ans2.append(k-cross[i][0][j][b])
if len(ans1) and len(ans2):
    print(max(max(ans1)*5,max(ans2)*10))
elif len(ans1):
    print(max(ans1)*5)
elif len(ans2):
    print(max(ans2)*10)
else:
    print("SAFE")

Submission status: Wrong Answer

Solution code:
#十字で合流する場合
n=int(input())
ud=[[[],[]] for i in range(200001)]
rl=[[[],[]] for i in range(200001)]
from bisect import *
cross=[[dict(),dict()] for i in range(4)]
for i in range(n):
    x,y,u=input().split()
    x,y=int(x),int(y)
    if u=="U":
        ud[x][0].append(y)
        if x+y in cross[0][1]:
            cross[0][1][x+y].append(x)
        else:
            cross[0][1][x+y]=[x]
        if x-y in cross[1][1]:
            cross[1][1][x-y].append(x)
        else:
            cross[1][1][x-y]=[x]
    elif u=="D":
        ud[x][1].append(y)
        if x+y in cross[3][1]:
            cross[3][1][x+y].append(x)
        else:
            cross[3][1][x+y]=[x]
        if x-y in cross[2][1]:
            cross[2][1][x-y].append(x)
        else:
            cross[2][1][x-y]=[x]
    elif u=="R":
        rl[y][0].append(x)
        if x+y in cross[0][0]:
            cross[0][0][x+y].append(x)
        else:
            cross[0][0][x+y]=[x]
        if x-y in cross[2][0]:
            cross[2][0][x-y].append(x)
        else:
            cross[2][0][x-y]=[x]
    else:
        rl[y][1].append(x)
        if x+y in cross[3][0]:
            cross[3][0][x+y].append(x)
        else:
            cross[3][0][x+y]=[x]
        if x-y in cross[1][0]:
            cross[1][0][x-y].append(x)
        else:
            cross[1][0][x-y]=[x]
for i in range(200001):
    ud[i][0].sort()
    ud[i][1].sort()
    rl[i][0].sort()
    rl[i][1].sort()
ans1=[]
for i in range(200001):
    l1,l2=len(ud[i][0]),len(ud[i][1])
    if l1 and l2:
        for j in ud[i][0]:
            b=bisect_left(ud[i][1],j)
            if b!=l2:
                ans1.append(ud[i][1][b]-j)
    l1,l2=len(rl[i][0]),len(rl[i][1])
    if l1 and l2:
        for j in rl[i][0]:
            b=bisect_left(rl[i][1],j)
            if b!=l2:
                ans1.append(rl[i][1][b]-j)
for i in range(4):
    for j in range(2):
        for k in cross[i][j]:
            cross[i][j][k].sort()
#print(cross)
ans2=[]
for i in range(4):
    for j in cross[i][1]:
        if j in cross[i][0]:
            l=len(cross[i][0][j])
            if i%2==1:
                for k in cross[i][1][j]:
                    b=bisect_left(cross[i][0][j],k)
                if b!=l:
                    ans2.append(cross[i][0][j][b]-k)
            else:
                for k in cross[i][1][j]:
                    b=bisect_right(cross[i][0][j],k)-1
                if b!=-1:
                    ans2.append(cross[i][0][j][b]-k)
if len(ans1) and len(ans2):
    print(max(max(ans1)*5,max(ans2)*10))
elif len(ans1):
    print(max(ans1)*5)
elif len(ans2):
    print(max(ans2)*10)
else:
    print("SAFE")

Submission status: Wrong Answer

Solution code:
n = int((input()))
U, R, D, L = [], [], [], []
for _ in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    (U if d == 'U' else R if d == 'R' else D if d == 'D' else L).append((x, y))
INF = 1001001001001
ans = INF
def front_crash(u, d):
    global ans
    u.sort()
    d.sort()
    i = 0
    j = 0
    while i < len(u) and j < len(d):
        ut = [u[i][1]]
        while i + 1 < len(u) and u[i][0] == u[i+1][0]:
            i += 1
            ut.append(u[i][1])
        dt = []
        while j + 1 < len(d) and d[j+1][0] < u[i][0]:
            j += 1
        while j < len(d) and d[j][0] == u[i][0]:
            dt.append(d[j][1])
            j += 1
        q = 0
        for y1 in ut:
            while q < len(dt) and dt[q] < y1:
                q += 1
            if q == len(dt):
                break
            y2 = dt[q]
            ans = min(ans, (y2 - y1) * 5)
        i += 1
front_crash(U, D)
front_crash(*(list(map(lambda p: (p[1], p[0]), t)) for t in [R, L]))
from collections import defaultdict
from bisect import bisect_left
def side_crash(u, r):
    global ans
    d = defaultdict(list)
    u.sort()
    for x, y in u:
        d[x+y].append(x)
    for x, y in r:
        dxy = d[x+y]
        i = bisect_left(dxy, x)
        if i < len(dxy):
            ans = min(ans, (dxy[i] - x) * 10)
side_crash(U, R)
side_crash(*([(y, 200000 - x) for x, y in t] for t in [L, U]))
side_crash(*([(200000 - x, 200000 - y) for x, y in t] for t in [D, L]))
side_crash(*([(200000 - y, x) for x, y in t] for t in [R, D]))

print(ans if ans < INF else 'SAFE')

Submission status: Wrong Answer

Solution code:
n = int((input()))
U, R, D, L = [], [], [], []
for _ in range(n):
    x, y, d = input().split()
    x = int(x)
    y = int(y)
    (U if d == 'U' else R if d == 'R' else D if d == 'D' else L).append((x, y))
INF = 1001001001
ans = INF
def front_crash(u, d):
    global ans
    u.sort()
    d.sort()
    i = 0
    j = 0
    while i < len(u) and j < len(d):
        ut = [u[i][1]]
        while i + 1 < len(u) and u[i][0] == u[i+1][0]:
            i += 1
            ut.append(u[i][1])
        dt = []
        while j + 1 < len(d) and d[j+1][0] < u[i][0]:
            j += 1
        while j < len(d) and d[j][0] == u[i][0]:
            dt.append(d[j][1])
            j += 1
        q = 0
        for y1 in ut:
            while q < len(dt) and dt[q] < y1:
                q += 1
            if q == len(dt):
                break
            y2 = dt[q]
            ans = min(ans, (y2 - y1) * 5)
        i += 1
front_crash(U, D)
front_crash(*(list(map(lambda p: (p[1], p[0]), t)) for t in [R, L]))
from collections import defaultdict
from bisect import bisect_left
def side_crash(u, r):
    global ans
    d = defaultdict(list)
    u.sort()
    for x, y in u:
        d[x+y].append(x)
    for x, y in r:
        dxy = d[x+y]
        i = bisect_left(dxy, x)
        if i < len(dxy):
            ans = min(ans, (dxy[i] - x) * 10)
side_crash(U, R)
side_crash(*([(y, 200000 - x) for x, y in t] for t in [L, U]))
side_crash(*([(200000 - x, 200000 - y) for x, y in t] for t in [D, L]))
side_crash(*([(200000 - y, x) for x, y in t] for t in [R, D]))

print(ans if ans < INF else 'SAFE')

Submission status: Wrong Answer

Solution code:
n=int(input())
ver=[]
hor=[]
diagr=[]
diagl=[]
INF=10**9
for i in range(200001):
  ver.append([[],[]])
  hor.append([[],[]])
for i in range(-200000,200001):
  diagr.append([[],[],[],[]])
  diagl.append([[],[],[],[]])
for i in range(n):
  x,y,u=map(str,input().split())
  x=int(x)
  y=int(y)
  if u=='U':
    ver[x][0].append(y)
    diagr[x-y+200000][0].append(x)
    diagl[x+y][0].append(x)
  if u=='D':
    ver[x][1].append(y)
    diagr[x-y+200000][1].append(x)
    diagl[x+y][1].append(x)
  if u=='R':
    hor[y][0].append(x)
    diagr[x-y+200000][2].append(x)
    diagl[x+y][2].append(x)
  if u=='L':
    hor[y][1].append(x)
    diagr[x-y+200000][3].append(x)
    diagl[x+y][3].append(x)
ans=INF
for i in range(200001):
  if len(ver[i][0])>0 and len(ver[i][1])>0:
    ver[i][0].sort()
    ver[i][1].sort()
    if ver[i][0][0]>ver[i][1][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(ver[i][1])
    t=len(ver[i][0])
    while pointer1<t:
      while pointer<s and pointer1<t and ver[i][1][pointer]<ver[i][0][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(ver[i][1][pointer]-ver[i][0][pointer1])//2)
      pointer1+=1
for i in range(200001):
  if len(hor[i][0])>0 and len(hor[i][1])>0:
    hor[i][0].sort()
    hor[i][1].sort()
    if hor[i][0][0]>hor[i][1][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(hor[i][1])
    t=len(hor[i][0])
    while pointer1<t:
      while pointer<s and pointer1<t and hor[i][1][pointer]<hor[i][0][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(hor[i][1][pointer]-hor[i][0][pointer1])//2)
      pointer1+=1
for i in range(400001):
  if len(diagl[i][0])>0 and len(diagl[i][2])>0:
    diagl[i][0].sort()
    diagl[i][2].sort()
    if diagl[i][2][0]>diagl[i][0][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(diagl[i][0])
    t=len(diagl[i][2])
    while pointer1<t:
      while pointer<s and pointer1<t and diagl[i][0][pointer]<diagl[i][2][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(diagl[i][0][pointer]-diagl[i][2][pointer1]))
      pointer1+=1
  if len(diagl[i][1])>0 and len(diagl[i][3])>0:
    diagl[i][1].sort()
    diagl[i][3].sort()
    if diagl[i][1][0]>diagl[i][3][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(diagl[i][3])
    t=len(diagl[i][1])
    while pointer1<t:
      while pointer<s and pointer1<t and diagl[i][3][pointer]<diagl[i][1][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(diagl[i][3][pointer]-diagl[i][1][pointer1]))
      pointer1+=1
for i in range(400001):
  if len(diagr[i][0])>0 and len(diagr[i][3])>0:
    diagr[i][0].sort()
    diagr[i][3].sort()
    if diagr[i][0][0]>diagr[i][3][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(diagr[i][3])
    t=len(diagr[i][0])
    while pointer1<t:
      while pointer<s and pointer1<t and diagr[i][3][pointer]<diagr[i][0][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(diagr[i][3][pointer]-diagr[i][0][pointer1]))
      pointer1+=1
  if len(diagr[i][1])>0 and len(diagr[i][2])>0:
    diagr[i][1].sort()
    diagr[i][2].sort()
    if diagr[i][2][0]>diagr[i][1][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(diagr[i][1])
    t=len(diagr[i][2])
    while pointer1<t:
      while pointer<s and pointer1<t and diagr[i][1][pointer]<diagr[i][2][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(diagr[i][1][pointer]-diagr[i][2][pointer1]))
      pointer1+=1
if ans==INF:
  print('SAFE')
else:
  print(ans*10)

Submission status: Wrong Answer

Solution code:
n=int(input())
ver=[]
hor=[]
diagr=[]
diagl=[]
INF=10**9
for i in range(200001):
  ver.append([[],[]])
  hor.append([[],[]])
for i in range(-200000,200001):
  diagr.append([[],[],[],[]])
  diagl.append([[],[],[],[]])
for i in range(n):
  x,y,u=map(str,input().split())
  x=int(x)
  y=int(y)
  if u=='U':
    ver[x][0].append(y)
    diagr[x-y+200000][0].append(x)
    diagl[x+y][0].append(x)
  if u=='D':
    ver[x][1].append(y)
    diagr[x-y+200000][1].append(x)
    diagl[x+y][1].append(x)
  if u=='R':
    hor[y][0].append(x)
    diagr[x-y+200000][2].append(x)
    diagl[x+y][2].append(x)
  if u=='L':
    hor[y][1].append(x)
    diagr[x-y+200000][3].append(x)
    diagl[x+y][3].append(x)
ans=INF
for i in range(200001):
  if len(ver[i][0])>0 and len(ver[i][1])>0:
    ver[i][0].sort()
    ver[i][1].sort()
    if ver[i][0][0]>ver[i][1][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(ver[i][1])
    t=len(ver[i][0])
    while pointer1<t:
      while pointer<s and pointer1<t and ver[i][1][pointer]<ver[i][0][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(ver[i][1][pointer]-ver[i][0][pointer1])//2)
      pointer1+=1
for i in range(400001):
  if len(diagl[i][0])>0 and len(diagl[i][2])>0:
    diagl[i][0].sort()
    diagl[i][2].sort()
    if diagl[i][2][0]>diagl[i][0][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(diagl[i][0])
    t=len(diagl[i][2])
    while pointer1<t:
      while pointer<s and pointer1<t and diagl[i][0][pointer]<diagl[i][2][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(diagl[i][0][pointer]-diagl[i][2][pointer1]))
      pointer1+=1
  if len(diagl[i][1])>0 and len(diagl[i][3])>0:
    diagl[i][1].sort()
    diagl[i][3].sort()
    if diagl[i][1][0]>diagl[i][3][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(diagl[i][3])
    t=len(diagl[i][1])
    while pointer1<t:
      while pointer<s and pointer1<t and diagl[i][3][pointer]<diagl[i][1][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(diagl[i][3][pointer]-diagl[i][1][pointer1]))
      pointer1+=1
for i in range(400001):
  if len(diagr[i][0])>0 and len(diagr[i][3])>0:
    diagr[i][0].sort()
    diagr[i][3].sort()
    if diagr[i][0][0]>diagr[i][3][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(diagr[i][3])
    t=len(diagr[i][0])
    while pointer1<t:
      while pointer<s and pointer1<t and diagr[i][3][pointer]<diagr[i][0][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(diagr[i][3][pointer]-diagr[i][0][pointer1]))
      pointer1+=1
  if len(diagr[i][1])>0 and len(diagr[i][2])>0:
    diagr[i][1].sort()
    diagr[i][2].sort()
    if diagr[i][2][0]>diagr[i][1][-1]:
      continue
    pointer1=0
    pointer=0
    s=len(diagr[i][1])
    t=len(diagr[i][2])
    while pointer1<t:
      while pointer<s and pointer1<t and diagr[i][1][pointer]<diagr[i][2][pointer1]:
        pointer+=1
      if pointer==s:
        break
      ans=min(ans,(diagr[i][1][pointer]-diagr[i][2][pointer1]))
      pointer1+=1
if ans==INF:
  print('SAFE')
else:
  print(ans*10)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
from bisect import bisect_left ,bisect_right
#bisect_left(a,x):a[i]>=xとなるような最小のi.
#昇順ソートされたリストaに昇順を崩さずxを挿入できる位置s(0-index)を返す.
#a=[1,3,5,7,9,11,13,15,17,19]
#s = bisect_left(a,4)
#s=2
# d = defaultdict(int)で0で初期化
# d = defaultdict(lambda: 100)で100で初期化
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])
R1 = defaultdict(list)
R2 = defaultdict(list)
L1 = defaultdict(list)
L2 = defaultdict(list)
U = defaultdict(list)
R = defaultdict(list)

R1u = defaultdict(bool)
R2u = defaultdict(bool)
L1u = defaultdict(bool)
L2u = defaultdict(bool)
Uu = defaultdict(bool)
Ru = defaultdict(bool)


M = 10000000
for x, y, u in a:
    if u == 1:
        R1[y - x].append(x)
        R2[x + y].append(x)
        R[y].append(x)
    elif u == 2:
        L1[x + y].append(x)
        L2[y - x].append(x)
        if not Ru[y]:
            R[y].sort()
            Ru[y] = True
        k = bisect_right(R[y], x)
        if k > 0:
            M = min((x - R[y][k-1]) * 5, M)

    elif u == 3:
        if not L2u[y - x]:
            L2[y - x].sort()
            L2u[y - x] = True
        k = bisect_left(L2[y - x], x-1)
        if k < len(L2[y - x]):
            M = min(M, (L2[y - x][k] - x) * 10)
        
        if not R2[x + y]:
            R2[x + y].sort()
            R2u[x + y] = True
        k = bisect_right(R2[x + y], x)
        if k > 0:
            M = min(M, (x - R2[x + y][k-1]) * 10)
        
        U[x].append(y)
    else:
        if not L1u[x + y]:
            L1[x + y].sort()
            L1u[x + y] = True
        k = bisect_left(L1[x + y], x-1)
        if k < len(L1[x + y]):
            M = min(M, (L1[x + y][k] - x) * 10)

        if not R1u[y - x]:
            R1[y - x].sort()
            R1u[y - x] = True
        k = bisect_right(R1[y - x], x)
        if k > 0:
            M = min(M, (x - R1[y - x][k-1]) * 10)

        if not Uu[x]:
            U[y].sort()
            Uu[y] = True
        k = bisect_right(U[x], y)
        if k > 0 :
            M = min((y - U[x][k-1]) * 5, M)
print(M if M < 10000000 else "SAFE")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

ANS=1<<100

N=int(input())
L=[]
R=[]
U=[]
D=[]

for i in range(N):
    x,y,c=input().split()
    if c=="L":
        L.append((int(x),int(y)))

    if c=="R":
        R.append((int(x),int(y)))

    if c=="U":
        U.append((int(x),int(y)))

    if c=="D":
        D.append((int(x),int(y)))

L.sort(key=itemgetter(0))
R.sort(key=itemgetter(0))
L.sort(key=itemgetter(1))
R.sort(key=itemgetter(1))

indr=0
for indl in range(len(L)):
    while indr<len(R) and R[indr][1]<L[indl][1]:
        indr+=1

    while indr<len(R) and R[indr][1]==L[indl][1] and R[indr][0]<L[indl][0]:
        ANS=min(ANS,(L[indl][0]-R[indr][0])*5)
        indr+=1
        
U.sort(key=itemgetter(1))
D.sort(key=itemgetter(1))
U.sort(key=itemgetter(0))
D.sort(key=itemgetter(0))

indd=0
for indu in range(len(U)):
    while indd<len(D) and D[indd][0]<U[indu][0]:
        indd+=1
        
    while indd<len(D) and U[indu][0]==D[indd][0] and U[indu][1]<D[indd][1]:
        ANS=min(ANS,(D[indd][1]-U[indu][1])*5)
        indd+=1

U.sort(key=itemgetter(0))
R.sort(key=itemgetter(0))
U.sort(key=lambda x:x[0]+x[1])
R.sort(key=lambda x:x[0]+x[1])

indr=0
for indu in range(len(U)):
    while indr<len(R) and R[indr][0]+R[indr][1]<U[indu][0]+U[indu][1]:
        indr+=1
    while indr<len(R) and R[indr][0]+R[indr][1]==U[indu][0]+U[indu][1] and R[indr][0]<U[indu][0]:
        ANS=min(ANS,(U[indu][0]-R[indr][0])*10)
        indr+=1

U.sort(key=itemgetter(0))
L.sort(key=itemgetter(0))
U.sort(key=lambda x:x[0]-x[1])
L.sort(key=lambda x:x[0]-x[1])

indl=0
for indu in range(len(U)):
    while indl<len(L) and L[indl][0]-L[indl][1]<U[indu][0]-U[indu][1]:
        indl+=1
    while indl<len(L) and L[indl][0]-L[indl][1]==U[indu][0]-U[indu][1] and L[indl][0]>U[indu][0]:
        ANS=min(ANS,(L[indl][0]-U[indu][0])*10)
        indl+=1

D.sort(key=itemgetter(0))
R.sort(key=itemgetter(0))
D.sort(key=lambda x:x[0]-x[1])
R.sort(key=lambda x:x[0]-x[1])

indr=0
for indd in range(len(D)):
    while indr<len(R) and R[indr][0]-R[indr][1]<D[indd][0]-D[indd][1]:
        indr+=1
    while indr<len(R) and R[indr][0]-R[indr][1]==D[indd][0]-D[indd][1] and R[indr][0]<D[indd][0]:
        ANS=min(ANS,(D[indd][0]-R[indr][0])*10)
        indr+=1

D.sort(key=itemgetter(0))
L.sort(key=itemgetter(0))
D.sort(key=lambda x:x[0]+x[1])
L.sort(key=lambda x:x[0]+x[1])

indl=0
for indd in range(len(D)):
    while indl<len(L) and L[indl][0]+L[indl][1]<D[indd][0]+D[indd][1]:
        indl+=1
    while indl<len(L) and L[indl][0]+L[indl][1]==D[indd][0]+D[indd][1] and L[indl][0]>D[indd][0]:
        ANS=min(ANS,(L[indl][0]-D[indd][0])*10)
        indl+=1


if ANS==1<<100:
    print("SAFE")
else:
    print(ANS)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from collections import defaultdict

n = int(input())
up = [defaultdict(list), defaultdict(list), defaultdict(list)]
dp = [defaultdict(list), defaultdict(list), defaultdict(list)]
lp = [defaultdict(list), defaultdict(list), defaultdict(list)]
rp = [defaultdict(list), defaultdict(list), defaultdict(list)]

for _ in range(n):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    if u == 'U':
        up[0][x].append(y)
        up[1][x + y].append(x)
        up[2][x - y].append(x)
    elif u == 'D':
        dp[0][x].append(y)
        dp[1][x + y].append(x)
        dp[2][x - y].append(x)
    elif u == 'L':
        lp[0][y].append(x)
        lp[1][x + y].append(x)
        lp[2][x - y].append(x)
    else:
        rp[0][y].append(x)
        rp[1][x + y].append(x)
        rp[2][x - y].append(x)


def crush_time(planes1, planes2, idx):
    result = INF
    for xy in planes1[idx]:
        if xy not in planes2[idx]:
            continue
        s = planes1[idx][xy]
        s.sort()
        for x in planes2[idx][xy]:
            i = bisect(s, x)
            if i > 0:
                result = min(result, x - s[i - 1])
    return result


INF = 10 ** 18

ans = min(
    crush_time(up, dp, 0) * 5,
    crush_time(rp, lp, 0) * 5,
    crush_time(rp, up, 1) * 10,
    crush_time(dp, lp, 1) * 10,
    crush_time(up, lp, 2) * 10,
    crush_time(rp, dp, 2) * 10,
)

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

Submission status: Wrong Answer

Solution code:
N=int(input())
XYU=[tuple(input().split()) for _ in range(N)]
U=R=D=L=[]
for x,y,u in XYU:
    x,y = int(x),int(y)
    if u=="U":
        U.append((x,y))
    elif u=="D":
        D.append((x,y))
    elif u=="L":
        L.append((x,y))
    else:
        R.append((x,y))
ans=[10**9]
def z(A):
    A.sort()
    n=p=-10**9
    for k,c,a in A:
        if k!=n:
            if a==1:
                n=k
                p=c
            continue
        if a==1:
            p=c
            continue
        if (c-p)*5<ans[0]:
            ans[0]=(c-p)*5
z([(x,y,1) for x, y in U]+[(x,y,-1) for x,y in D])
z([(y,x,1) for x, y in R]+[(y,x,-1) for x,y in L])
z([(x+y,x-y,1) for x, y in R]+[(x+y,x-y,-1) for x,y in U])
z([(x+y,x-y,1) for x, y in D]+[(x+y,x-y,-1) for x,y in L])
z([(x-y,x+y,1) for x,y in U]+[(x-y,x+y,-1) for x,y in L])
z([(x-y,x+y,1) for x,y in R]+[(x-y,x+y,-1) for x,y in D])
print("SAFE" if ans[0]>=10**9 else ans[0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

ANS=1<<100

N=int(input())
L=[]
R=[]
U=[]
D=[]

for i in range(N):
    x,y,c=input().split()
    if c=="L":
        L.append((int(x),int(y)))

    if c=="R":
        R.append((int(x),int(y)))

    if c=="U":
        U.append((int(x),int(y)))

    if c=="D":
        D.append((int(x),int(y)))

L.sort(key=itemgetter(1))
R.sort(key=itemgetter(1))

indr=0
for indl in range(len(L)):
    while indr<len(R) and R[indr][1]<L[indl][1]:
        indr+=1
    if indr<len(R) and L[indl][1]==R[indr][1] and R[indr][0]<L[indl][0]:
        ANS=min(ANS,(L[indl][0]-R[indr][0])*5)

U.sort(key=itemgetter(0))
D.sort(key=itemgetter(0))

indd=0
for indu in range(len(U)):
    while indd<len(D) and D[indd][0]<U[indu][0]:
        indd+=1
    if indd<len(D) and U[indu][0]==D[indd][0] and U[indu][1]<D[indd][1]:
        ANS=min(ANS,(D[indd][1]-U[indu][1])*5)

U.sort(key=lambda x:x[0]+x[1])
R.sort(key=lambda x:x[0]+x[1])

indr=0
for indu in range(len(U)):
    while indr<len(R) and R[indr][0]+R[indr][1]<U[indu][0]+U[indu][1]:
        indr+=1
    if indr<len(R) and R[indr][0]+R[indr][1]==U[indu][0]+U[indu][1] and R[indr][0]<U[indu][0]:
        ANS=min(ANS,(U[indu][0]-R[indr][0])*10)

U.sort(key=lambda x:x[0]-x[1])
L.sort(key=lambda x:x[0]-x[1])

indl=0
for indu in range(len(U)):
    while indl<len(L) and L[indl][0]-L[indl][1]<U[indu][0]-U[indu][1]:
        indl+=1
    if indl<len(L) and L[indl][0]-L[indl][1]==U[indu][0]-U[indu][1] and L[indl][0]>U[indu][0]:
        ANS=min(ANS,(L[indl][0]-U[indu][0])*10)

D.sort(key=lambda x:x[0]-x[1])
R.sort(key=lambda x:x[0]-x[1])

indr=0
for indd in range(len(D)):
    while indr<len(R) and R[indr][0]-R[indr][1]<D[indd][0]-D[indd][1]:
        indr+=1
    if indr<len(R) and R[indr][0]-R[indr][1]==D[indd][0]-D[indd][1] and R[indr][0]<D[indd][0]:
        ANS=min(ANS,(D[indd][0]-R[indr][0])*10)

D.sort(key=lambda x:x[0]+x[1])
L.sort(key=lambda x:x[0]+x[1])

indl=0
for indd in range(len(D)):
    while indl<len(L) and L[indl][0]+L[indl][1]<D[indd][0]+D[indd][1]:
        indl+=1
    if indl<len(L) and L[indl][0]+L[indl][1]==D[indd][0]+D[indd][1] and L[indl][0]>D[indd][0]:
        ANS=min(ANS,(L[indl][0]-D[indd][0])*10)


if ANS==1<<100:
    print("SAFE")
else:
    print(ANS)