Problem p02605 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from operator import itemgetter

n = readint()

ans = 10**10

only = [[[]for i in range(2*10**5+1)]for j in range(4)]
plus = [[[]for i in range(4*10**5+1)]for j in range(4)]
minus = [[[]for i in range(4*10**5+1)]for j in range(4)]
a = ['D','U','L','R']
for i in range(n):
    x,y,z = readstrs()
    x = int(x)
    y = int(y)
    b = a.index(z)
    if b<2:
        only[b][x].append(y)
    else:
        only[b][y].append(x)
    plus[b][x+y].append(x)
    minus[b][x-y].append(x)

for m in [0,2]:
    for i in range(2*10**5+1):
        a = only[m][i]
        b = only[m+1][i]
        if a and b:
            a.sort()
            b.sort()
            k = 0
            j = 0
            while k<len(a) and j<len(b):
                if a[k]>b[j]:
                    ans = min(ans,(a[k]-b[j])/2)
                    j += 1
                else:
                    k += 1

for p,q in [[2,1],[0,3]]:
    for i in range(4*10**5+1):
        a = minus[p][i]
        b = minus[q][i]
        if a and b:
            a.sort()
            b.sort()
            k = 0
            j = 0
            while k<len(a) and j<len(b):
                if a[k]>b[j]:
                    ans = min(ans,a[k]-b[j])
                    j += 1
                else:
                    k += 1

for p,q in [[1,3],[2,0]]:
    for i in range(4*10**5+1):
        a = plus[p][i]
        b = plus[q][i]
        if a and b:
            a.sort()
            b.sort()
            k = 0
            j = 0
            while k<len(a) and j<len(b):
                if a[k]>b[j]:
                    ans = min(ans,a[k]-b[j])
                    j += 1
                else:
                    k += 1

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

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from operator import itemgetter

n = readint()

ans = 10**10

u = []
d = []
l = []
r = []
uu = [[]for i in range(2*10**5+1)]
dd = [[]for i in range(2*10**5+1)]
ll = [[]for i in range(2*10**5+1)]
rr = [[]for i in range(2*10**5+1)]
for i in range(n):
    x,y,a = readstrs()
    x = int(x)
    y = int(y)
    if a=='U':
        u.append([x,y,x+y,x-y])
        uu[x].append(y)
    elif a == 'D':
        d.append([x,y,x+y,x-y])
        dd[x].append(y)
    elif a == 'L':
        l.append([x,y,x+y,x-y])
        ll[y].append(x)
    elif a == 'R':
        r.append([x,y,x+y,x-y])
        rr[y].append(x)

for i in range(2*10**5+1):
    if uu[i] and dd[i]:
        uu[i].sort()
        dd[i].sort()
        lenu = len(uu[i])
        lend = len(dd[i])
        k = 0
        j = 0
        while k<lenu and j<lend:
            if dd[i][j]>uu[i][k]:
                ans = min(ans,(dd[i][j]-uu[i][k])/2)
                k += 1
            else:
                j += 1
    if ll[i] and rr[i]:
        ll[i].sort()
        rr[i].sort()
        lenl = len(ll[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenl and j<lenr:
            if ll[i][j]>rr[i][k]:
                ans = min(ans,(ll[i][j]-rr[i][k])/2)
                k += 1
            else:
                j += 1

uu = [[]for i in range(4*10**5+100)]
dd = [[]for i in range(4*10**5+100)]
ll = [[]for i in range(4*10**5+100)]
rr = [[]for i in range(4*10**5+100)]

for a in u:
    uu[a[3]].append(a[0])
for a in d:
    dd[a[3]].append(a[0])    
for a in l:
    ll[a[3]].append(a[0])
for a in r:
    rr[a[3]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and ll[i]:
        uu[i].sort()
        ll[i].sort()
        lenu = len(uu[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while k<lenu and j<lenl:
            if ll[i][j]>uu[i][k]:
                ans = min(ans,ll[i][j]-uu[i][k])
                k += 1
            else:
                j += 1
    if dd[i] and rr[i]:
        dd[i].sort()
        rr[i].sort()
        lend = len(dd[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while j<lend and k<lenr:
            if dd[i][j]>rr[i][k]:
                ans = min(ans,dd[i][j]-rr[i][k])
                k += 1
            else:
                j += 1

        
uu = [[]for i in range(4*10**5+100)]
dd = [[]for i in range(4*10**5+100)]
ll = [[]for i in range(4*10**5+100)]
rr = [[]for i in range(4*10**5+100)]

for a in u:
    uu[a[2]].append(a[0])
for a in d:
    dd[a[2]].append(a[0])    
for a in l:
    ll[a[2]].append(a[0])
for a in r:
    rr[a[2]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and rr[i]:
        uu[i].sort()
        rr[i].sort()
        lenu = len(uu[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenu and j<lenr:
            if rr[i][j]<uu[i][k]:
                ans = min(ans,-rr[i][j]+uu[i][k])
                j += 1
            else:
                k += 1
    if dd[i] and ll[i]:
        dd[i].sort()
        ll[i].sort()
        lend = len(dd[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while j<lend and k<lenl:
            if dd[i][j]<ll[i][k]:
                ans = min(ans,-dd[i][j]+ll[i][k])
                j += 1
            else:
                k += 1

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

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from operator import itemgetter

n = readint()

ans = 10**10

u = []
d = []
l = []
r = []
uu = [[]for i in range(2*10**5+1)]
dd = [[]for i in range(2*10**5+1)]
ll = [[]for i in range(2*10**5+1)]
rr = [[]for i in range(2*10**5+1)]
for i in range(n):
    x,y,a = readstrs()
    x = int(x)
    y = int(y)
    if a=='U':
        u.append([x,y,x+y,x-y])
        uu[x].append(y)
    elif a == 'D':
        d.append([x,y,x+y,x-y])
        dd[x].append(y)
    elif a == 'L':
        l.append([x,y,x+y,x-y])
        ll[y].append(x)
    elif a == 'R':
        r.append([x,y,x+y,x-y])
        rr[y].append(x)

for i in range(2*10**5+1):
    if uu[i] and dd[i]:
        uu[i].sort()
        dd[i].sort()
        lenu = len(uu[i])
        lend = len(dd[i])
        k = 0
        j = 0
        while k<lenu and j<lend:
            if dd[i][j]>uu[i][k]:
                ans = min(ans,(dd[i][j]-uu[i][k])/2)
                k += 1
            else:
                j += 1
    if ll[i] and rr[i]:
        ll[i].sort()
        rr[i].sort()
        lenl = len(ll[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenl and j<lenr:
            if ll[i][j]>rr[i][k]:
                ans = min(ans,(ll[i][j]-rr[i][k])/2)
                k += 1
            else:
                j += 1

uu = [[]for i in range(4*10**5+1)]
dd = [[]for i in range(4*10**5+1)]
ll = [[]for i in range(4*10**5+1)]
rr = [[]for i in range(4*10**5+1)]

for a in u:
    uu[a[3]].append(a[0])
for a in d:
    dd[a[3]].append(a[0])    
for a in l:
    ll[a[3]].append(a[0])
for a in r:
    rr[a[3]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and ll[i]:
        uu[i].sort()
        ll[i].sort()
        lenu = len(uu[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while k<lenu and j<lenl:
            if ll[i][j]>uu[i][k]:
                ans = min(ans,ll[i][j]-uu[i][k])
                k += 1
            else:
                j += 1
    if dd[i] and rr[i]:
        dd[i].sort()
        rr[i].sort()
        lend = len(dd[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while j<lend and k<lenr:
            if dd[i][j]>rr[i][k]:
                ans = min(ans,dd[i][j]-rr[i][k])
                k += 1
            else:
                j += 1

        
uu = [[]for i in range(4*10**5+1)]
dd = [[]for i in range(4*10**5+1)]
ll = [[]for i in range(4*10**5+1)]
rr = [[]for i in range(4*10**5+1)]

for a in u:
    uu[a[2]].append(a[0])
for a in d:
    dd[a[2]].append(a[0])    
for a in l:
    ll[a[2]].append(a[0])
for a in r:
    rr[a[2]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and rr[i]:
        uu[i].sort()
        rr[i].sort()
        lenu = len(uu[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenu and j<lenr:
            if rr[i][j]<uu[i][k]:
                ans = min(ans,-rr[i][j]+uu[i][k])
                j += 1
            else:
                k += 1
    if dd[i] and ll[i]:
        dd[i].sort()
        ll[i].sort()
        lend = len(dd[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while j<lend and k<lenl:
            if dd[i][j]<ll[i][k]:
                ans = min(ans,-dd[i][j]+ll[i][k])
                j += 1
            else:
                k += 1

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

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from operator import itemgetter

n = readint()

ans = 10**10

u = []
d = []
l = []
r = []
uu = [[]for i in range(2*10**5+1)]
dd = [[]for i in range(2*10**5+1)]
ll = [[]for i in range(2*10**5+1)]
rr = [[]for i in range(2*10**5+1)]
for i in range(n):
    x,y,a = readstrs()
    x = int(x)
    y = int(y)
    if a=='U':
        u.append([x,y,x+y,x-y])
        uu[x].append(y)
    elif a == 'D':
        d.append([x,y,x+y,x-y])
        dd[x].append(y)
    elif a == 'L':
        l.append([x,y,x+y,x-y])
        ll[y].append(x)
    elif a == 'R':
        r.append([x,y,x+y,x-y])
        rr[y].append(x)

for i in range(2*10**5+1):
    if uu[i] and dd[i]:
        uu[i].sort()
        dd[i].sort()
        lenu = len(uu[i])
        lend = len(dd[i])
        k = 0
        j = 0
        while k<lenu and j<lend:
            if dd[i][j]>uu[i][k]:
                ans = min(ans,(dd[i][j]-uu[i][k])//2)
                k += 1
            else:
                j += 1
    if ll[i] and rr[i]:
        ll[i].sort()
        rr[i].sort()
        lenl = len(ll[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenl and j<lenr:
            if ll[i][j]>rr[i][k]:
                ans = min(ans,(ll[i][j]-rr[i][k])//2)
                k += 1
            else:
                j += 1

uu = [[]for i in range(4*10**5+1)]
dd = [[]for i in range(4*10**5+1)]
ll = [[]for i in range(4*10**5+1)]
rr = [[]for i in range(4*10**5+1)]

for a in u:
    uu[a[3]].append(a[0])
for a in d:
    dd[a[3]].append(a[0])    
for a in l:
    ll[a[3]].append(a[0])
for a in r:
    rr[a[3]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and ll[i]:
        uu[i].sort()
        ll[i].sort()
        lenu = len(uu[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while k<lenu and j<lenl:
            if ll[i][j]>uu[i][k]:
                ans = min(ans,ll[i][j]-uu[i][k])
                k += 1
            else:
                j += 1
    if dd[i] and rr[i]:
        dd[i].sort()
        rr[i].sort()
        lend = len(dd[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while j<lend and k<lenr:
            if dd[i][j]>rr[i][k]:
                ans = min(ans,dd[i][j]-rr[i][k])
                k += 1
            else:
                j += 1

        
uu = [[]for i in range(4*10**5+1)]
dd = [[]for i in range(4*10**5+1)]
ll = [[]for i in range(4*10**5+1)]
rr = [[]for i in range(4*10**5+1)]

for a in u:
    uu[a[2]].append(a[0])
for a in d:
    dd[a[2]].append(a[0])    
for a in l:
    ll[a[2]].append(a[0])
for a in r:
    rr[a[2]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and rr[i]:
        uu[i].sort()
        rr[i].sort()
        lenu = len(uu[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenu and j<lenr:
            if rr[i][j]<uu[i][k]:
                ans = min(ans,-rr[i][j]+uu[i][k])
                j += 1
            else:
                k += 1
    if dd[i] and ll[i]:
        dd[i].sort()
        ll[i].sort()
        lend = len(dd[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while j<lend and k<lenl:
            if dd[i][j]<ll[i][k]:
                ans = min(ans,-dd[i][j]+ll[i][k])
                j += 1
            else:
                k += 1

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

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from operator import itemgetter

n = readint()

ans = 10**10

u = []
d = []
l = []
r = []
uu = [[]for i in range(2*10**5+1)]
dd = [[]for i in range(2*10**5+1)]
ll = [[]for i in range(2*10**5+1)]
rr = [[]for i in range(2*10**5+1)]
for i in range(n):
    x,y,a = readstrs()
    x = int(x)
    y = int(y)
    if a=='U':
        u.append([x,y,x+y,x-y])
        uu[x].append(y)
    elif a == 'D':
        d.append([x,y,x+y,x-y])
        dd[x].append(y)
    elif a == 'L':
        l.append([x,y,x+y,x-y])
        ll[y].append(x)
    elif a == 'R':
        r.append([x,y,x+y,x-y])
        rr[y].append(x)

for i in range(2*10**5+1):
    if uu[i] and dd[i]:
        uu[i].sort()
        dd[i].sort()
        lenu = len(uu[i])
        lend = len(dd[i])
        k = 0
        j = 0
        while k<lenu and j<lend:
            if dd[i][j]>uu[i][k]:
                ans = min(ans,(dd[i][j]-uu[i][k])//2)
                k += 1
            else:
                j += 1
    if ll[i] and rr[i]:
        ll[i].sort()
        rr[i].sort()
        lenl = len(ll[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenl and j<lenr:
            if ll[i][j]>rr[i][k]:
                ans = min(ans,(ll[i][j]-rr[i][k])//2)
                k += 1
            else:
                j += 1

uu = [[]for i in range(4*10**5+1)]
dd = [[]for i in range(4*10**5+1)]
ll = [[]for i in range(4*10**5+1)]
rr = [[]for i in range(4*10**5+1)]

for a in u:
    uu[a[3]].append(a[0])
for a in d:
    dd[a[3]].append(a[0])    
for a in l:
    ll[a[3]].append(a[0])
for a in r:
    rr[a[3]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and ll[i]:
        uu[i].sort()
        ll[i].sort()
        lenu = len(uu[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while k<lenu and j<lenl:
            if ll[i][j]>uu[i][k]:
                ans = min(ans,ll[i][j]-uu[i][k])
                k += 1
            else:
                j += 1
    if dd[i] and rr[i]:
        dd[i].sort()
        rr[i].sort()
        lend = len(dd[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while j<lend and k<lenr:
            if dd[i][j]>rr[i][k]:
                ans = min(ans,dd[i][j]-rr[i][k])
                k += 1
            else:
                j += 1

        
uu = [[]for i in range(4*10**5+1)]
dd = [[]for i in range(4*10**5+1)]
ll = [[]for i in range(4*10**5+1)]
rr = [[]for i in range(4*10**5+1)]

for a in u:
    uu[a[2]].append(a[0])
for a in d:
    dd[a[2]].append(a[0])    
for a in l:
    ll[a[2]].append(a[0])
for a in r:
    rr[a[2]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and rr[i]:
        uu[i].sort()
        rr[i].sort()
        lenu = len(uu[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenu and j<lenr:
            if rr[i][j]<uu[i][k]:
                ans = min(ans,-rr[i][j]+uu[i][k])
                k += 1
            else:
                j += 1
    if dd[i] and ll[i]:
        dd[i].sort()
        ll[i].sort()
        lend = len(dd[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while j<lend and k<lenl:
            if dd[i][j]<ll[i][k]:
                ans = min(ans,-dd[i][j]+ll[i][k])
                k += 1
            else:
                j += 1

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

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from operator import itemgetter

n = readint()

ans = 10**10

u = []
d = []
l = []
r = []
uu = [[]for i in range(2*10**5+1)]
dd = [[]for i in range(2*10**5+1)]
ll = [[]for i in range(2*10**5+1)]
rr = [[]for i in range(2*10**5+1)]
for i in range(n):
    x,y,a = readstrs()
    x = int(x)
    y = int(y)
    if a=='U':
        u.append([x,y,x+y,x-y])
        uu[x].append(y)
    elif a == 'D':
        d.append([x,y,x+y,x-y])
        dd[x].append(y)
    elif a == 'L':
        l.append([x,y,x+y,x-y])
        ll[y].append(x)
    elif a == 'R':
        r.append([x,y,x+y,x-y])
        rr[y].append(x)

for i in range(2*10**5+1):
    if uu[i] and dd[i]:
        uu[i].sort()
        dd[i].sort()
        lenu = len(uu[i])
        lend = len(dd[i])
        k = 0
        j = 0
        while k<lenu and j<lend:
            if dd[i][j]>uu[i][k]:
                ans = min(ans,(dd[i][j]-uu[i][k])//2)
                k += 1
            else:
                j += 1
    if ll[i] and rr[i]:
        ll[i].sort()
        rr[i].sort()
        lenl = len(ll[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenl and j<lenr:
            if ll[i][j]>rr[i][k]:
                ans = min(ans,(ll[i][j]-rr[i][k])//2)
                k += 1
            else:
                j += 1

uu = [[]for i in range(4*10**5+1)]
dd = [[]for i in range(4*10**5+1)]
ll = [[]for i in range(4*10**5+1)]
rr = [[]for i in range(4*10**5+1)]

for a in u:
    uu[a[3]].append(a[0])
for a in d:
    dd[a[3]].append(a[0])    
for a in l:
    ll[a[3]].append(a[0])
for a in r:
    rr[a[3]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and ll[i]:
        uu[i].sort()
        ll[i].sort()
        lenu = len(uu[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while k<lenu and j<lenl:
            if ll[i][j]>uu[i][k]:
                ans = min(ans,ll[i][j]-uu[i][k])
                k += 1
            else:
                j += 1
    if dd[i] and rr[i]:
        dd[i].sort()
        rr[i].sort()
        lend = len(dd[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lend and j<lenr:
            if dd[i][j]>rr[i][k]:
                ans = min(ans,dd[i][j]-rr[i][k])
                k += 1
            else:
                j += 1

        
uu = [[]for i in range(4*10**5+1)]
dd = [[]for i in range(4*10**5+1)]
ll = [[]for i in range(4*10**5+1)]
rr = [[]for i in range(4*10**5+1)]

for a in u:
    uu[a[2]].append(a[0])
for a in d:
    dd[a[2]].append(a[0])    
for a in l:
    ll[a[2]].append(a[0])
for a in r:
    rr[a[2]].append(a[0])

for i in range(4*10**5+1):
    if uu[i] and rr[i]:
        uu[i].sort()
        rr[i].sort()
        lenu = len(uu[i])
        lenr = len(rr[i])
        k = 0
        j = 0
        while k<lenu and j<lenr:
            if rr[i][j]<uu[i][k]:
                ans = min(ans,-rr[i][j]+uu[i][k])
                k += 1
            else:
                j += 1
    if dd[i] and ll[i]:
        dd[i].sort()
        ll[i].sort()
        lend = len(dd[i])
        lenl = len(ll[i])
        k = 0
        j = 0
        while k<lend and j<lenl:
            if dd[i][j]<ll[i][k]:
                ans = min(ans,-dd[i][j]+ll[i][k])
                k += 1
            else:
                j += 1

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