Problem p02605 (python)

Fixed submission:
import sys
input = sys.stdin.readline

INF = 10**18

N = int(input())
X = [0] * N
Y = [0] * N
U = [''] * N
for i in range(N):
    x, y, u = input().split()
    X[i] = int(x)
    Y[i] = int(y)
    U[i] = u
M = 200000

def rotate():
    s = 'ULDR'
    for i in range(N):
        X[i], Y[i] = M - Y[i], X[i]
        U[i] = s[(s.index(U[i]) + 1) % 4]

def calc1():
    v = [[] for _ in range(M+1)]
    for x, y, u in zip(X, Y, U):
        if u in 'RL':
            v[y].append((x, u))
    ret = INF
    for y in range(M+1):
        v[y].sort(key=lambda p: p[0])
        for i in range(len(v[y])-1):
            if v[y][i][1] == 'R' and v[y][i+1][1] == 'L':
                ret = min(ret, (v[y][i+1][0] - v[y][i][0]) * 5)
    return ret

def calc2():
    v = [[] for _ in range(2*M+1)]
    for x, y, u in zip(X, Y, U):
        if u in 'UR':
            v[x+y].append((x, u))
    ret = INF
    for xy in range(2*M+1):
        v[xy].sort(key=lambda p: p[0])
        for i in range(len(v[xy])-1):
            if v[xy][i][1] == 'R' and v[xy][i+1][1] == 'U':
                ret = min(ret, (v[xy][i+1][0] - v[xy][i][0]) * 10)
    return ret

ans = INF
for i in range(4):
    ans = min(ans, calc1(), calc2())
    rotate()
print(ans if ans < INF else 'SAFE')

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
X = [0] * N
Y = [0] * N
U = [''] * N
for i in range(N):
    x, y, u = input().split()
    X[i] = int(x)
    Y[i] = int(y)
    U[i] = u

def calc(X, Y, U):
    mx = min(X)
    for i in range(N):
        X[i] -= mx
    my = min(Y)
    for i in range(N):
        Y[i] -= my
    Mx = max(X)
    My = max(Y)
    up = [[] for _ in range(Mx+1)]
    down = [[] for _ in range(Mx+1)]
    left = [[] for _ in range(My+1)]
    right = [[] for _ in range(My+1)]
    for x, y, u in zip(X, Y, U):
        if u == 'U':
            up[x].append(y)
        if u == 'D':
            down[x].append(y)
        if u == 'L':
            left[y].append(x)
        if u == 'R':
            right[y].append(x)
    ret = float('inf')
    for x in range(Mx+1):
        up[x].sort()
        down[x].sort()
        s = t = 0
        while s < len(up[x]):
            while t < len(down[x]) and up[x][s] > down[x][t]:
                t += 1
            if t < len(down[x]):
                ret = min(ret, (down[x][t] - up[x][t]) * 5)
            s += 1
    for y in range(My+1):
        right[y].sort()
        left[y].sort()
        s = t = 0
        while s < len(right[y]):
            while t < len(left[y]) and right[y][s] > left[y][t]:
                t += 1
            if t < len(left[y]):
                ret = min(ret, (left[y][t] - right[y][t]) * 5)
            s += 1
    return ret


ans = calc(X, Y, U)
nX = [X[i] - Y[i] for i in range(N)]
nY = [X[i] + Y[i] for i in range(N)]

U1 = []
for u in U:
    if u == 'R':
        U1.append('U')
    elif u == 'L':
        U1.append('D')
    else:
        U1.append(u)
ans = min(ans, calc(nX, nY, U1))

U2 = []
for u in U:
    if u == 'U':
        U2.append('L')
    elif u == 'D':
        U2.append('R')
    else:
        U2.append(u)
ans = min(ans, calc(nX, nY, U2))

print(ans if ans < float('inf') else 'SAFE')