Problem:


Score: 600 points

Problem Statement

M-kun is a brilliant air traffic controller.

On the display of his radar, there are N airplanes numbered 1, 2, ..., N, all flying at the same altitude.

Each of the airplanes flies at a constant speed of 0.1 per second in a constant direction. The current coordinates of the airplane numbered i are (X_i, Y_i), and the direction of the airplane is as follows:

if U_i is U, it flies in the positive y direction;

if U_i is R, it flies in the positive x direction;

if U_i is D, it flies in the negative y direction;

if U_i is L, it flies in the negative x direction.

To help M-kun in his work, determine whether there is a pair of airplanes that will collide with each other if they keep flying as they are now.

If there is such a pair, find the number of seconds after which the first collision will happen.

We assume that the airplanes are negligibly small so that two airplanes only collide when they reach the same coordinates simultaneously.

Constraints

1 \leq N \leq 200000

0 \leq X_i, Y_i \leq 200000

U_i is U, R, D, or L.

The current positions of the N airplanes, (X_i, Y_i), are all distinct.

N, X_i, and Y_i are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1 U_1
X_2 Y_2 U_2
X_3 Y_3 U_3
:
X_N Y_N U_N

Output

If there is a pair of airplanes that will collide with each other if they keep flying as they are now, print an integer representing the number of seconds after which the first collision will happen.

If there is no such pair, print SAFE.

Sample Input 1

2
11 1 U
11 47 D

Sample Output 1

230

If the airplanes keep flying as they are now, two airplanes numbered 1 and 2 will reach the coordinates (11, 24) simultaneously and collide.  

Sample Input 2

4
20 30 U
30 20 R
20 10 D
10 20 L

Sample Output 2

SAFE

No pair of airplanes will collide.

Sample Input 3

8
168 224 U
130 175 R
111 198 D
121 188 L
201 116 U
112 121 R
145 239 D
185 107 L

Sample Output 3

100



Sample input:
2
11 1 U
11 47 D


Sample output:
230

Submission status: Accepted

Solution code:
INF = 2000000000


def calc_xx(A, B, mult, comp_field, diff_field):
    AA = list(sorted(A, key=lambda pp: (pp[comp_field], pp[diff_field])))
    BB = list(sorted(B, key=lambda pp: (pp[comp_field], pp[diff_field])))

    a = 0
    b = 0

    min_time = INF
    while a < len(A) and b < len(B):
        # 衝突判定 (ソートの重複値の全組み合わせで検証)
        if AA[a][comp_field] == BB[b][comp_field]:
            astart = a
            asame = a + 1
            while asame < len(A) and AA[asame][comp_field] == AA[a][comp_field]:
                asame += 1
            aend = asame - 1

            bstart = b
            bsame = b + 1
            while bsame < len(B) and BB[bsame][comp_field] == BB[b][comp_field]:
                bsame += 1
            bend = bsame - 1

            # まさかの二重DP
            aa = astart
            bb = bstart
            while aa <= aend and bb <= bend:
                diff = BB[bb][diff_field] - AA[aa][diff_field]
                if diff > 0:
                    hit_time = diff * mult
                    min_time = min(min_time, hit_time)

                if aa == aend:
                    bb += 1
                elif bb == bend:
                    aa += 1
                elif BB[bb][diff_field] > AA[aa][diff_field]:
                    aa += 1
                else:
                    bb += 1

            a = aend + 1
            b = bend + 1

        elif a == len(A) - 1:
            b += 1
        elif b == len(B) - 1:
            a += 1
        elif AA[a][comp_field] > BB[b][comp_field]:
            b += 1
        elif AA[a][comp_field] < BB[b][comp_field]:
            a += 1
        else:
            raise Exception

    return min_time


def main():
    N = int(input())
    PLANES = []

    U = []
    R = []
    D = []
    L = []
    for i in range(N):
        # x=c[0]
        # y=c[1]
        # u=c[2]
        p = input().split()
        p[0] = int(p[0])
        p[1] = int(p[1])

        pp = [p[0], p[1], (p[0] + p[1]), (p[1] - p[0])]

        PLANES.append(p)
        if p[2] == "U":
            U.append(pp)
        elif p[2] == "R":
            R.append(pp)
        elif p[2] == "D":
            D.append(pp)
        else:
            L.append(pp)

    min_time = min(
        calc_xx(R, U, 10, 2, 0),
        calc_xx(U, D, 5, 0, 1),
        calc_xx(U, L, 10, 3, 0),
        calc_xx(R, D, 10, 3, 0),
        calc_xx(R, L, 5, 1, 0),
        calc_xx(D, L, 10, 2, 0),
    )

    if min_time == INF:
        print("SAFE")
    else:
        print(min_time)


main()

Submission status: Accepted

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()

ans=[]
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:
                ans.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:
                ans.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()

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:
                        ans.append(2*cross[i][0][j][b]-2*k)
            else:
                for k in cross[i][1][j]:
                    b=bisect_right(cross[i][0][j],k)-1
                    if b!=-1:
                        ans.append(2*k-2*cross[i][0][j][b])

if len(ans):
    print(min(ans)*5)
else:
    print("SAFE")

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import heapq as hq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    planes = [list(SI().split()) for _ in range(N)]

    XS = [[] for _ in range(200001)]
    YS = [[] for _ in range(200001)]
    ZS = [[] for _ in range(400001)]
    WS = [[] for _ in range(400001)]
    for plane in planes:
        x, y, u = int(plane[0]), int(plane[1]), plane[2]
        XS[x].append((y, u))
        YS[y].append((x, u))
        ZS[x+y].append((x, u))
        WS[x-y+200000].append((x, u))
    for X in XS:
        hq.heapify(X)
    for Y in YS:
        hq.heapify(Y)
    for Z in ZS:
        hq.heapify(Z)
    for W in WS:
        hq.heapify(W)

    ans = float("inf")

    for X in XS:
        if len(X) <= 1:
            continue
        c = -1
        for _ in range(len(X)):
            k, u = hq.heappop(X)
            if u == "U":
                c = k
            if u == "D" and c >= 0:
                ans = min(ans, (k - c)*5)
                c = -1

    for Y in YS:
        if len(Y) <= 1:
            continue
        c = -1
        for _ in range(len(Y)):
            k, u = hq.heappop(Y)
            if u == "R":
                c = k
            if u == "L" and c >= 0:
                ans = min(ans, (k - c)*5)
                c = -1

    for Z in ZS:
        if len(Z) <= 1:
            continue
        c = -1
        d = -1
        for _ in range(len(Z)):
            k, u = hq.heappop(Z)
            if u == "R":
                c = k
            if u == "D":
                d = k
            if u == "U" and c >= 0:
                ans = min(ans, (k - c)*10)
                c = -1
            if u == "L" and d >= 0:
                ans = min(ans, (k - d)*10)
                d = -1

    for W in WS:
        if len(W) <= 1:
            continue
        c = -1
        d = -1
        for _ in range(len(W)):
            k, u = hq.heappop(W)
            if u == "R":
                c = k
            if u == "U":
                d = k
            if u == "D" and c >= 0:
                ans = min(ans, (k - c)*10)
                c = -1
            if u == "L" and d >= 0:
                ans = min(ans, (k - d)*10)
                d = -1

    if ans == float("inf"):
        print("SAFE")
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

N=int(input())

X1={}
X2={}

X={}
Y={}

for i in range(N):
    x,y,u=input().split()
    x=int(x)
    y=int(y)
    if x+y not in X1:
        X1[x+y]=[[x,u]]
    else:
        X1[x+y].append([x,u])
    if y-x not in X2:
        X2[y-x]=[[x,u]]
    else:
        X2[y-x].append([x,u])
    if x not in X:
        X[x]=[[y,u]]
    else:
        X[x].append([y,u])
    if y not in Y:
        Y[y]=[[x,u]]
    else:
        Y[y].append([x,u])


Dead=10**9


for k,v in X1.items():
    D=-1
    R=-1
    v.sort()
    #print(v)
    for a,u in v:
        if u=="D":
            D=a
        elif u=="R":
            R=a
        elif u=="L":
            if D>=0:
                Dead=min(Dead,(a-D)*10)
        elif u=="U":
            if R>=0:
                Dead=min(Dead,(a-R)*10)
for k,v in X2.items():
    U=-1
    R=-1
    v.sort()
    #print(v)
    for a,u in v:
        if u=="U":
            U=a
        elif u=="R":
            R=a
        elif u=="L":
            if U>=0:
                Dead=min(Dead,(a-U)*10)
        elif u=="D":
            if R>=0:
                Dead=min(Dead,(a-R)*10)
for k,v in X.items():
    U=-1
    v.sort()
    #print(v)
    for a,u in v:
        if u=="U":
            U=a
        elif u=="D":
            if U>=0:
                Dead=min(Dead,(a-U)*5)
for k,v in Y.items():
    R=-1
    v.sort()
    #print(v)
    for a,u in v:
        if u=="R":
            R=a
        elif u=="L":
            if R>=0:
                Dead=min(Dead,(a-R)*5)
if Dead==10**9:
    print("SAFE")
else:
    print(Dead)

Submission status: Accepted

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 < len(d) and d[j][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: Accepted

Solution code:
n = int(input())
b = 2000001
u = []; r = []; d = []; l = []
for i in range(n):
    A = list(input().split())
    a = [int(A[0]), int(A[1])]
    if A[2] == "U":
        u.append(a)
    elif A[2] == "R":
        r.append(a)
    elif A[2] == "D":
        d.append(a)
    else:
        l.append(a)
u1 = {}; d1 = {}
for i in range(len(u)):
    if u[i][0] not in u1:
        u1[u[i][0]] = []
    u1[u[i][0]].append(u[i][1])
for i in range(len(d)):
    if d[i][0] not in d1:
        d1[d[i][0]] = []
    d1[d[i][0]].append(d[i][1])
for i in range(200001):
    if i in u1 and i in d1:
        u1[i].sort(reverse=True)
        d1[i].sort(reverse=True)
        for j in range(len(u1[i])):
            for k in range(len(d1[i])):
                if u1[i][-1] < d1[i][-1]:
                    b = min(b, (d1[i][-1]-u1[i][-1])*5)
                    break
                else:
                    d1[i].pop()
            u1[i].pop()
r1 = {}; l1 = {}
for i in range(len(r)):
    if r[i][1] not in r1:
        r1[r[i][1]] = []
    r1[r[i][1]].append(r[i][0])
for i in range(len(l)):
    if l[i][1] not in l1:
        l1[l[i][1]] = []
    l1[l[i][1]].append(l[i][0])
for i in range(200001):
    if i in r1 and i in l1:
        r1[i].sort(reverse=True)
        l1[i].sort(reverse=True)
        for j in range(len(r1[i])):
            for k in range(len(l1[i])):
                if r1[i][-1] < l1[i][-1]:
                    b = min(b, (l1[i][-1]-r1[i][-1])*5)
                    break
                else:
                    l1[i].pop()
            r1[i].pop()
u2 = {}; r2 = {}
for i in range(len(u)):
    if u[i][0]+u[i][1] not in u2:
        u2[u[i][0]+u[i][1]] = []
    u2[u[i][0]+u[i][1]].append(u[i][0])
for i in range(len(r)):
    if r[i][0]+r[i][1] not in r2:
        r2[r[i][0]+r[i][1]] = []
    r2[r[i][0]+r[i][1]].append(r[i][0])
for i in range(400001):
    if i in u2 and i in r2:
        u2[i].sort(reverse=True)
        r2[i].sort(reverse=True)
        for j in range(len(r2[i])):
            for k in range(len(u2[i])):
                if r2[i][-1] < u2[i][-1]:
                    b = min(b, (u2[i][-1]-r2[i][-1])*10)
                    break
                else:
                    u2[i].pop()
            r2[i].pop()
l2 = {}; d2 = {}
for i in range(len(l)):
    if l[i][0]+l[i][1] not in l2:
        l2[l[i][0]+l[i][1]] = []
    l2[l[i][0]+l[i][1]].append(l[i][0])
for i in range(len(d)):
    if d[i][0]+d[i][1] not in d2:
        d2[d[i][0]+d[i][1]] = []
    d2[d[i][0]+d[i][1]].append(d[i][0])
for i in range(400001):
    if i in l2 and i in d2:
        l2[i].sort(reverse=True)
        d2[i].sort(reverse=True)
        for j in range(len(d2[i])):
            for k in range(len(l2[i])):
                if d2[i][-1] < l2[i][-1]:
                    b = min(b, (l2[i][-1]-d2[i][-1])*10)
                    break
                else:
                    l2[i].pop()
            d2[i].pop()
l3 = {}; u3 = {}
for i in range(len(l)):
    if l[i][0]-l[i][1] not in l3:
        l3[l[i][0]-l[i][1]] = []
    l3[l[i][0]-l[i][1]].append(l[i][0])
for i in range(len(u)):
    if u[i][0]-u[i][1] not in u3:
        u3[u[i][0]-u[i][1]] = []
    u3[u[i][0]-u[i][1]].append(u[i][0])
for i in range(-200000, 200001):
    if i in l3 and i in u3:
        l3[i].sort(reverse=True)
        u3[i].sort(reverse=True)
        for j in range(len(u3[i])):
            for k in range(len(l3[i])):
                if u3[i][-1] < l3[i][-1]:
                    b = min(b, (l3[i][-1]-u3[i][-1])*10)
                    break
                else:
                    l3[i].pop()
            u3[i].pop()
d3 = {}; r3 = {}
for i in range(len(d)):
    if d[i][0]-d[i][1] not in d3:
        d3[d[i][0]-d[i][1]] = []
    d3[d[i][0]-d[i][1]].append(d[i][0])
for i in range(len(r)):
    if r[i][0]-r[i][1] not in r3:
        r3[r[i][0]-r[i][1]] = []
    r3[r[i][0]-r[i][1]].append(r[i][0])
for i in range(-200000, 200001):
    if i in d3 and i in r3:
        d3[i].sort(reverse=True)
        r3[i].sort(reverse=True)
        for j in range(len(r3[i])):
            for k in range(len(d3[i])):
                if r3[i][-1] < d3[i][-1]:
                    b = min(b, (d3[i][-1]-r3[i][-1])*10)
                    break
                else:
                    d3[i].pop()
            r3[i].pop()
print("SAFE") if b == 2000001 else print(b)

Submission status: Accepted

Solution code:
n = int(input())
b = 2000001
u = []; r = []; d = []; l = []
for i in range(n):
    A = list(input().split())
    a = [int(A[0]), int(A[1])]
    if A[2] == "U":
        u.append(a)
    elif A[2] == "R":
        r.append(a)
    elif A[2] == "D":
        d.append(a)
    else:
        l.append(a)
#ud
u1 = {}; d1 = {}
for i in range(len(u)):
    if u[i][0] not in u1:
        u1[u[i][0]] = []
    u1[u[i][0]].append(u[i][1])
for i in range(len(d)):
    if d[i][0] not in d1:
        d1[d[i][0]] = []
    d1[d[i][0]].append(d[i][1])
for i in range(200001):
    if i in u1 and i in d1:
        u1[i].sort(reverse=True)
        d1[i].sort(reverse=True)
        for j in range(len(u1[i])):
            for k in range(len(d1[i])):
                if u1[i][-1] < d1[i][-1]:
                    b = min(b, (d1[i][-1]-u1[i][-1])*5)
                    break
                else:
                    d1[i].pop()
            u1[i].pop()

#rl
r1 = {}; l1 = {}
for i in range(len(r)):
    if r[i][1] not in r1:
        r1[r[i][1]] = []
    r1[r[i][1]].append(r[i][0])
for i in range(len(l)):
    if l[i][1] not in l1:
        l1[l[i][1]] = []
    l1[l[i][1]].append(l[i][0])
for i in range(200001):
    if i in r1 and i in l1:
        r1[i].sort(reverse=True)
        l1[i].sort(reverse=True)
        for j in range(len(r1[i])):
            for k in range(len(l1[i])):
                if r1[i][-1] < l1[i][-1]:
                    b = min(b, (l1[i][-1]-r1[i][-1])*5)
                    break
                else:
                    l1[i].pop()
            r1[i].pop()
u2 = {}; r2 = {}
for i in range(len(u)):
    if u[i][0]+u[i][1] not in u2:
        u2[u[i][0]+u[i][1]] = []
    u2[u[i][0]+u[i][1]].append(u[i][0])
for i in range(len(r)):
    if r[i][0]+r[i][1] not in r2:
        r2[r[i][0]+r[i][1]] = []
    r2[r[i][0]+r[i][1]].append(r[i][0])
for i in range(400001):
    if i in u2 and i in r2:
        u2[i].sort(reverse=True)
        r2[i].sort(reverse=True)
        for j in range(len(r2[i])):
            for k in range(len(u2[i])):
                if r2[i][-1] < u2[i][-1]:
                    b = min(b, (u2[i][-1]-r2[i][-1])*10)
                    break
                else:
                    u2[i].pop()
            r2[i].pop()
l2 = {}; d2 = {}
for i in range(len(l)):
    if l[i][0]+l[i][1] not in l2:
        l2[l[i][0]+l[i][1]] = []
    l2[l[i][0]+l[i][1]].append(l[i][0])
for i in range(len(d)):
    if d[i][0]+d[i][1] not in d2:
        d2[d[i][0]+d[i][1]] = []
    d2[d[i][0]+d[i][1]].append(d[i][0])
for i in range(400001):
    if i in l2 and i in d2:
        l2[i].sort(reverse=True)
        d2[i].sort(reverse=True)
        for j in range(len(d2[i])):
            for k in range(len(l2[i])):
                if d2[i][-1] < l2[i][-1]:
                    b = min(b, (l2[i][-1]-d2[i][-1])*10)
                    break
                else:
                    l2[i].pop()
            d2[i].pop()
l3 = {}; u3 = {}
for i in range(len(l)):
    if l[i][0]-l[i][1] not in l3:
        l3[l[i][0]-l[i][1]] = []
    l3[l[i][0]-l[i][1]].append(l[i][0])
for i in range(len(u)):
    if u[i][0]-u[i][1] not in u3:
        u3[u[i][0]-u[i][1]] = []
    u3[u[i][0]-u[i][1]].append(u[i][0])
for i in range(-200000, 200001):
    if i in l3 and i in u3:
        l3[i].sort(reverse=True)
        u3[i].sort(reverse=True)
        for j in range(len(u3[i])):
            for k in range(len(l3[i])):
                if u3[i][-1] < l3[i][-1]:
                    b = min(b, (l3[i][-1]-u3[i][-1])*10)
                    break
                else:
                    l3[i].pop()
            u3[i].pop()
d3 = {}; r3 = {}
for i in range(len(d)):
    if d[i][0]-d[i][1] not in d3:
        d3[d[i][0]-d[i][1]] = []
    d3[d[i][0]-d[i][1]].append(d[i][0])
for i in range(len(r)):
    if r[i][0]-r[i][1] not in r3:
        r3[r[i][0]-r[i][1]] = []
    r3[r[i][0]-r[i][1]].append(r[i][0])
for i in range(-200000, 200001):
    if i in d3 and i in r3:
        d3[i].sort(reverse=True)
        r3[i].sort(reverse=True)
        for j in range(len(r3[i])):
            for k in range(len(d3[i])):
                if r3[i][-1] < d3[i][-1]:
                    b = min(b, (d3[i][-1]-r3[i][-1])*10)
                    break
                else:
                    d3[i].pop()
            r3[i].pop()
print("SAFE") if b == 2000001 else print(b)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    s = 'UDLR'
    g = [list() for _ in range(4)]
    for _ in range(n):
        x, y, u = input().split()
        g[s.index(u)].append((int(x), int(y)))


    def calc(a, b):
        a.sort()
        b.sort()
        idx = 0
        m = len(b)
        res = 10 ** 9
        for x, y in a:
            while idx < m and (b[idx][0] < x or b[idx][0] == x and b[idx][1] < y):
                idx += 1
            if idx >= m:
                break
            if b[idx][0] == x and b[idx][1] >= y:
                res = min(res, b[idx][1] - y)
        return res * 5

    res1 = calc(g[0], g[1])
    res2 = calc([(y, x) for x, y in g[3]], [(y, x) for x, y in g[2]])
    res3 = calc([(x+y, x-y) for x, y in g[3]], [(x+y, x-y) for x, y in g[0]])
    res4 = calc([(x+y, x-y) for x, y in g[1]], [(x+y, x-y) for x, y in g[2]])
    res5 = calc([(x-y, x+y) for x, y in g[0]], [(x-y, x+y) for x, y in g[2]])
    res6 = calc([(x-y, x+y) for x, y in g[3]], [(x-y, x+y) for x, y in g[1]])
    ans = min(res1, res2, res3, res4, res5, res6)
    if ans > 10**9:
        print('SAFE')
    else:
        print(ans)
    return

solve()

Submission status: Accepted

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])*5)
      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])*5)
      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])*10)
      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])*10)
      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])*10)
      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])*10)
      pointer1+=1
if ans==INF:
  print('SAFE')
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
from bisect import bisect_right
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_right(L2[y - x], x)
        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_right(L1[x + y], x)
        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: Accepted

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),reverse=True)
D.sort(key=itemgetter(1),reverse=True)
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),reverse=True)
L.sort(key=itemgetter(0),reverse=True)
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),reverse=True)
L.sort(key=itemgetter(0),reverse=True)
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)