Problem p02680 (python)

Fixed submission:
#!usr/bin/env python3
import sys
import bisect
from collections import deque
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

M = 3*10**9+1
M2 = (M-10**9)**2
n,m = LI()
p = LIR(n)
q = LIR(m)
fx = set([-M,0,M])
fy = set([-M,0,M])
for i in range(n):
    p[i][0] <<= 1
    p[i][1] <<= 1
    p[i][2] <<= 1
    a,b,c = p[i]
    fy.add(a)
    fy.add(b)
    fy.add(b+1)
    fx.add(c)
    fx.add(c+1)

for i in range(m):
    q[i][0] <<= 1
    q[i][1] <<= 1
    q[i][2] <<= 1
    d,e,f = q[i]
    fy.add(d)
    fy.add(d+1)
    fx.add(e)
    fx.add(f)
    fx.add(f+1)
fy = list(fy)
fx = list(fx)
fy.sort()
fx.sort()
s = [0]*len(fx)*len(fy)
for a,b,c in p:
    ai = bisect.bisect_left(fy,a)
    bi = bisect.bisect_left(fy,b)
    ci = bisect.bisect_left(fx,c)
    ka = ai*len(fx)
    kb = (bi+1)*len(fx)
    s[ka+ci] += 1
    s[kb+ci] -= 1
    s[ka+ci+1] -= 1
    s[kb+ci+1] += 1
for d,e,f in q:
    di = bisect.bisect_left(fy,d)
    ei = bisect.bisect_left(fx,e)
    fi = bisect.bisect_left(fx,f)
    kd = di*len(fx)
    kdd = kd+len(fx)
    s[kd+ei] += 1
    s[kd+fi+1] -= 1
    s[kdd+ei] -= 1
    s[kdd+fi+1] += 1
for i in range(len(fy)):
    k = i*len(fx)
    for j in range(len(fx)-1):
        ind = k+j
        s[ind+1] += s[ind]
for i in range(len(fy)-1):
    k = i*len(fx)
    for j in range(len(fx)-1):
        ind = k+j
        s[ind+len(fx)] += s[ind]
sx = bisect.bisect_left(fx,0)
sy = bisect.bisect_left(fy,0)
nh,nw = len(fy)-1,len(fx)-1
for i in range(nw-1):
    fx[i+1] >>= 1
    fx[i] = fx[i+1]-fx[i]
for i in range(nh-1):
    fy[i+1] >>= 1
    fy[i] = fy[i+1]-fy[i]
ans = fx[sx]*fy[sy]
q = deque()
q.append((sy,sx))
f = [1]*nh*nw
f[sy*nw+sx] = 0
d = [(1,0),(-1,0),(0,1),(0,-1)]
while q:
    y,x = q.popleft()
    for dy,dx in d:
        ny,nx = y+dy,x+dx
        if 0 <= ny < nh and 0 <= nx < nw:
            ind = ny*nw+nx
            if f[ind] and not s[ind+ny]:
                if ny < 1 or nx < 1 or ny+1 >= nh or nx+1 >= nw:
                    print("INF")
                    quit()
                ans += fx[nx]*fy[ny]
                f[ind] = 0
                q.append((ny,nx))
print(ans)

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
import sys
import bisect
from itertools import accumulate
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    n,m = LI()
    p = LIR(n)
    q = LIR(m)
    fx = [-float("inf"),float("inf")]
    fy = [-float("inf"),float("inf")]
    for i in range(n):
        p[i][0] *= 10
        p[i][1] *= 10
        p[i][2] *= 10
        a,b,c = p[i]
        fy.append(a)
        fy.append(b)
        fy.append(b+1)
        fx.append(c)
        fx.append(c+1)

    for i in range(m):
        q[i][0] *= 10
        q[i][1] *= 10
        q[i][2] *= 10
        d,e,f = q[i]
        fy.append(d)
        fy.append(d+1)
        fx.append(e)
        fx.append(f)
        fx.append(f+1)
    fy = list(set(fy))
    fx = list(set(fx))
    fy.sort()
    fx.sort()
    h = len(fy)+1
    w = len(fx)+1
    s = [0]*h*w
    for a,b,c in p:
        ai = bisect.bisect_left(fy,a)
        bi = bisect.bisect_left(fy,b)
        ci = bisect.bisect_left(fx,c)
        ka = ai*w
        kb = (bi+1)*w
        s[ka+ci] += 1
        s[kb+ci] -= 1
        s[ka+ci+1] -= 1
        s[kb+ci+1] += 1
    for d,e,f in q:
        di = bisect.bisect_left(fy,d)
        ei = bisect.bisect_left(fx,e)
        fi = bisect.bisect_left(fx,f)
        kd = di*w
        kdd = kd+w
        s[kd+ei] += 1
        s[kd+fi+1] -= 1
        s[kdd+ei] -= 1
        s[kdd+fi+1] += 1
    for i in range(h):
        for j in range(len(fx)):
            ind = i*w+j
            s[ind+1] += s[ind]
    for i in range(len(fy)):
        for j in range(w):
            ind = i*w+j
            s[ind+w] += s[ind]
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    sx = bisect.bisect_left(fx,0)
    sy = bisect.bisect_left(fy,0)
    nh,nw = len(fy)-1,len(fx)-1
    fx[1] //= 10
    fy[1] //= 10
    for i in range(1,nw-1):
        fx[i+1] = fx[i+1]//10
        fx[i] = fx[i+1]-fx[i]
    for i in range(1,nh-1):
        fy[i+1] = fy[i+1]//10
        fy[i] = fy[i+1]-fy[i]
    fx[0] = -fx[0]
    fy[0] = -fy[0]
    ans = fx[sx]*fy[sy]
    q = [(sy,sx)]
    f = [1]*nh*nw
    f[sy*nw+sx] = 0
    while q:
        y,x = q.pop()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < nh and 0 <= nx < nw:
                ind = ny*nw+nx
                if f[ind] and not s[ind+2*ny]:
                    k = fx[nx]*fy[ny]
                    if k >= float("inf"):
                        print("INF")
                        return
                    ans += k
                    f[ind] = 0
                    q.append((ny,nx))
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    p = LIR(n)
    q = LIR(m)
    fx = set([-float("inf"),0,float("inf")])
    fy = set([-float("inf"),0,float("inf")])
    for a,b,c in p:
        fy.add(a)
        fy.add(a+1e-1)
        fy.add(a-1e-1)
        fy.add(b)
        fy.add(b+1e-1)
        fy.add(b-1e-1)
        fx.add(c)
        fx.add(c+1e-1)
        fx.add(c-1e-1)

    for d,e,f in q:
        fy.add(d)
        fy.add(d+1e-1)
        fy.add(d-1e-1)
        fx.add(e)
        fx.add(e+1e-1)
        fx.add(e-1e-1)
        fx.add(f)
        fx.add(f+1e-1)
        fx.add(f-1e-1)
    fy = list(fy)
    fx = list(fx)
    fy.sort()
    fx.sort()
    h = len(fy)+1
    w = len(fx)+1
    s = [[0]*w for i in range(h)]
    for a,b,c in p:
        ai = bisect.bisect_left(fy,a)
        bi = bisect.bisect_left(fy,b)
        ci = bisect.bisect_left(fx,c)
        s[ai][ci] += 1
        s[bi+1][ci] -= 1
        s[ai][ci+1] -= 1
        s[bi+1][ci+1] += 1
    for d,e,f in q:
        di = bisect.bisect_left(fy,d)
        ei = bisect.bisect_left(fx,e)
        fi = bisect.bisect_left(fx,f)
        s[di][ei] += 1
        s[di][fi+1] -= 1
        s[di+1][ei] -= 1
        s[di+1][fi+1] += 1
    for i in range(h):
        for j in range(len(fx)):
            s[i][j+1] += s[i][j]
    for i in range(len(fy)):
        for j in range(w):
            s[i+1][j] += s[i][j]
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    ans = 0
    sx = bisect.bisect_left(fx,0)
    sy = bisect.bisect_left(fy,0)
    ans += round((fx[sx+1]-fx[sx])*(fy[sy+1]-fy[sy]))
    q = [(sy,sx)]
    nh,nw = len(fy)-1,len(fx)-1
    f = [[1]*nw for i in range(nh)]
    f[sy][sx] = 0
    while q:
        y,x = q.pop()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < nh and 0 <= nx < nw:
                if f[ny][nx] and not s[ny][nx]:
                    k = (fx[nx+1]-fx[nx])*(fy[ny+1]-fy[ny])
                    if k == float("inf"):
                        print("INF")
                        return
                    ans += round(k)
                    f[ny][nx] = 0
                    q.append((ny,nx))
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    p = LIR(n)
    q = LIR(m)
    fx = set([0])
    fy = set([0])
    for a,b,c in p:
        fy.add(a-1e-15)
        fy.add(a)
        fy.add(a+1e-15)
        fy.add(b-1e-15)
        fy.add(b)
        fy.add(b+1e-15)
        fx.add(c-1e-15)
        fx.add(c)
        fx.add(c+1e-15)

    for d,e,f in q:
        fy.add(d-1e-15)
        fy.add(d)
        fy.add(d+1e-15)
        fx.add(e-1e-15)
        fx.add(e)
        fx.add(e+1e-15)
        fx.add(f-1e-15)
        fx.add(f)
        fx.add(f+1e-15)
    fy = list(fy)
    fx = list(fx)
    fy.sort()
    fx.sort()
    h = len(fy)+1
    w = len(fx)+1
    s = [[0]*w for i in range(h)]
    for a,b,c in p:
        ai = bisect.bisect_left(fy,a)
        bi = bisect.bisect_left(fy,b)
        ci = bisect.bisect_left(fx,c)
        s[ai][ci] += 1
        s[bi+1][ci] -= 1
        s[ai][ci+1] -= 1
        s[bi+1][ci+1] += 1
    for d,e,f in q:
        di = bisect.bisect_left(fy,d)
        ei = bisect.bisect_left(fx,e)
        fi = bisect.bisect_left(fx,f)
        s[di][ei] += 1
        s[di][fi+1] -= 1
        s[di+1][ei] -= 1
        s[di+1][fi+1] += 1
    for i in range(h):
        for j in range(len(fx)):
            s[i][j+1] += s[i][j]
    for i in range(len(fy)):
        for j in range(w):
            s[i+1][j] += s[i][j]
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    ans = 0
    sx = bisect.bisect_left(fx,0)
    sy = bisect.bisect_left(fy,0)
    ans += (fx[sx+1]-fx[sx])*(fy[sy+1]-fy[sy])
    q = [(sy,sx)]
    nh,nw = len(fy)-1,len(fx)-1
    f = [[1]*nw for i in range(nh)]
    f[sy][sx] = 0
    while q:
        y,x = q.pop()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 < ny < nh and 0 < nx < nw:
                if f[ny][nx] and not s[ny][nx]:
                    ans += (fx[nx+1]-fx[nx])*(fy[ny+1]-fy[ny])
                    f[ny][nx] = 0
                    q.append((ny,nx))
    for i in range(1,nh):
        for j in range(1,nw):
            if s[i][j] == 0:
                if f[i][j]:
                    break
        else:
            continue
        break
    else:
        print("INF")
        return
    print(round(ans))
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    p = LIR(n)
    q = LIR(m)
    fx = set([0,float("inf")])
    fy = set([0,float("inf")])
    for a,b,c in p:
        fy.add(a-1e-15)
        fy.add(a)
        fy.add(a+1e-15)
        fy.add(b-1e-15)
        fy.add(b)
        fy.add(b+1e-15)
        fx.add(c-1e-15)
        fx.add(c)
        fx.add(c+1e-15)

    for d,e,f in q:
        fy.add(d-1e-15)
        fy.add(d)
        fy.add(d+1e-15)
        fx.add(e-1e-15)
        fx.add(e)
        fx.add(e+1e-15)
        fx.add(f-1e-15)
        fx.add(f)
        fx.add(f+1e-15)
    fy = list(fy)
    fx = list(fx)
    fy.sort()
    fx.sort()
    h = len(fy)+1
    w = len(fx)+1
    s = [[0]*w for i in range(h)]
    for a,b,c in p:
        ai = bisect.bisect_left(fy,a)
        bi = bisect.bisect_left(fy,b)
        ci = bisect.bisect_left(fx,c)
        s[ai][ci] += 1
        s[bi+1][ci] -= 1
        s[ai][ci+1] -= 1
        s[bi+1][ci+1] += 1
    for d,e,f in q:
        di = bisect.bisect_left(fy,d)
        ei = bisect.bisect_left(fx,e)
        fi = bisect.bisect_left(fx,f)
        s[di][ei] += 1
        s[di][fi+1] -= 1
        s[di+1][ei] -= 1
        s[di+1][fi+1] += 1
    for i in range(h):
        for j in range(len(fx)):
            s[i][j+1] += s[i][j]
    for i in range(len(fy)):
        for j in range(w):
            s[i+1][j] += s[i][j]
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    ans = 0
    sx = bisect.bisect_left(fx,0)
    sy = bisect.bisect_left(fy,0)
    ans += (fx[sx+1]-fx[sx])*(fy[sy+1]-fy[sy])
    q = [(sy,sx)]
    nh,nw = len(fy)-1,len(fx)-1
    f = [[1]*nw for i in range(nh)]
    f[sy][sx] = 0
    while q:
        y,x = q.pop()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 < ny < nh and 0 < nx < nw:
                if f[ny][nx] and not s[ny][nx]:
                    ans += (fx[nx+1]-fx[nx])*(fy[ny+1]-fy[ny])
                    f[ny][nx] = 0
                    q.append((ny,nx))
    for i in range(1,nh):
        for j in range(1,nw):
            if s[i][j] == 0:
                if f[i][j]:
                    break
        else:
            continue
        break
    else:
        print("INF")
        return
    print(round(ans))
    return

#Solve
if __name__ == "__main__":
    solve()