Problem p02680 (python)

Fixed submission:

N,M = map(int,input().split())

ts = {}
tlis = []

for i in range(N):
    B,C,A = map(int,input().split())

    if A not in ts:
        tlis.append(A)
        ts[A] = []
    ts[A].append([B,C])

ys = {}
ylis = []

for i in range(M):
    A,B,C = map(int,input().split())

    if A not in ys:
        ylis.append(A)
        ys[A] = []
    ys[A].append([B,C])

tlis.sort()
ylis.sort()

import bisect

nowi = bisect.bisect_right(tlis,0) - 1
nowj = bisect.bisect_right(ylis,0) - 1

#print (tlis,ylis,nowi,nowj)

for i in ts:
    
    ts[i].sort()

    new = []
    lastl = None
    lastr = None

    for tmp in ts[i]:
        nl,nr = tmp

        if lastl == None:
            lastl = nl
            lastr = nr

        elif lastr < nl:
            new.append([lastl,lastr])
            lastl = nl
            lastr = nr

        else:
            lastr = nr

    new.append([lastl,lastr])
    ts[i] = new

for i in ys:
    
    ys[i].sort()

    new = []
    lastl = None
    lastr = None

    for tmp in ys[i]:
        nl,nr = tmp

        if lastl == None:
            lastl = nl
            lastr = nr

        elif lastr < nl:
            new.append([lastl,lastr])
            lastl = nl
            lastr = nr

        else:
            lastr = nr

    new.append([lastl,lastr])
    ys[i] = new


from collections import deque

q = deque([ [nowi,nowj] ])
import sys
ans = 0

end = {}
end[(nowi,nowj)] = 1

if len(tlis) < 2 or len(ylis) < 2:
    print ("INF")
    sys.exit()

while len(q) > 0:

    ni,nj = q.popleft()

    
    if ni == -1 or nj == -1 or ni == len(tlis)-1 or nj == len(ylis)-1:
        print ("INF")
        sys.exit()

    up = ylis[nj]
    do = ylis[nj + 1]
    le = tlis[ni]
    ri = tlis[ni + 1]

    #print (ni,nj,up,do,le,ri)

    ans += (do-up) * (ri-le)

    #up
    flag = True

    nex = (ni,nj-1)

    if nex not in end:
        for tmp in ys[up]:
            L,R = tmp

            if L <= le and ri <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni,nj+1)
    flag = True

    if nex not in end:
        for tmp in ys[do]:
            L,R = tmp

            if L <= le and ri <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni-1,nj)
    flag = True
    if nex not in end:
        for tmp in ts[le]:
            L,R = tmp

            if L <= up and do <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni+1,nj)
    flag = True
    if nex not in end:
        for tmp in ts[ri]:
            L,R = tmp

            if L <= up and do <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

print (ans)

Buggy submission (verdict: Runtime Error):

N,M = map(int,input().split())

ts = {}
tlis = []

for i in range(N):
    B,C,A = map(int,input().split())

    if A not in ts:
        tlis.append(A)
        ts[A] = []
    ts[A].append([B,C])

ys = {}
ylis = []

for i in range(M):
    A,B,C = map(int,input().split())

    if A not in ys:
        ylis.append(A)
        ys[A] = []
    ys[A].append([B,C])

tlis.sort()
ylis.sort()

import bisect

nowi = bisect.bisect_left(tlis,0)
nowj = bisect.bisect_left(ylis,0)

#print (tlis,ylis,nowi,nowj)

for i in ts:
    
    ts[i].sort()

    new = []
    lastl = None
    lastr = None

    for tmp in ts[i]:
        nl,nr = tmp

        if lastl == None:
            lastl = nl
            lastr = nr

        elif lastr < nl:
            new.append([lastl,lastr])
            lastl = nl
            lastr = nr

        else:
            lastr = nr

    new.append([lastl,lastr])
    ts[i] = new

for i in ys:
    
    ys[i].sort()

    new = []
    lastl = None
    lastr = None

    for tmp in ys[i]:
        nl,nr = tmp

        if lastl == None:
            lastl = nl
            lastr = nr

        elif lastr < nl:
            new.append([lastl,lastr])
            lastl = nl
            lastr = nr

        else:
            lastr = nr

    new.append([lastl,lastr])
    ys[i] = new


from collections import deque

q = deque([ [nowi,nowj] ])
import sys
ans = 0

end = {}
end[(nowi,nowj)] = 1

while len(q) > 0:

    ni,nj = q.popleft()

    
    if ni == -1 or nj == -1 or ni == len(tlis)-1 or nj == len(ylis)-1:
        print ("INF")
        sys.exit()

    up = ylis[nj]
    do = ylis[nj + 1]
    le = tlis[ni]
    ri = tlis[ni + 1]

    #print (ni,nj,up,do,le,ri)

    ans += (do-up) * (ri-le)

    #up
    flag = True

    nex = (ni,nj-1)

    if nex not in end:
        for tmp in ys[up]:
            L,R = tmp

            if L <= le and ri <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni,nj+1)
    flag = True

    if nex not in end:
        for tmp in ys[do]:
            L,R = tmp

            if L <= le and ri <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni-1,nj)
    flag = True
    if nex not in end:
        for tmp in ts[le]:
            L,R = tmp

            if L <= up and do <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

    nex = (ni+1,nj)
    flag = True
    if nex not in end:
        for tmp in ts[ri]:
            L,R = tmp

            if L <= up and do <= R:
                flag = False
                break

        if flag:
            end[nex] = 1
            q.append([nex[0],nex[1]])

print (ans)