Problem:


Score: 600 points

Problem Statement

There is a grass field that stretches infinitely.

In this field, there is a negligibly small cow. Let (x, y) denote the point that is x\ \mathrm{cm} south and y\ \mathrm{cm} east of the point where the cow stands now. The cow itself is standing at (0, 0).

There are also N north-south lines and M east-west lines drawn on the field. The i-th north-south line is the segment connecting the points (A_i, C_i) and (B_i, C_i), and the j-th east-west line is the segment connecting the points (D_j, E_j) and (D_j, F_j).

What is the area of the region the cow can reach when it can move around as long as it does not cross the segments (including the endpoints)? If this area is infinite, print INF instead.

Constraints

All values in input are integers between -10^9 and 10^9  (inclusive).

1 \leq N, M \leq 1000

A_i < B_i\ (1 \leq i \leq N)

E_j < F_j\ (1 \leq j \leq M)

The point (0, 0) does not lie on any of the given segments.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
:
A_N B_N C_N
D_1 E_1 F_1
:
D_M E_M F_M

Output

If the area of the region the cow can reach is infinite, print INF; otherwise, print an integer representing the area in \mathrm{cm^2}.

(Under the constraints, it can be proved that the area of the region is always an integer if it is not infinite.)

Sample Input 1

5 6
1 2 0
0 1 1
0 2 2
-3 4 -1
-2 6 3
1 0 1
0 1 2
2 0 2
-1 -4 5
3 -2 4
1 2 4

Sample Output 1

13

The area of the region the cow can reach is 13\ \mathrm{cm^2}.

Sample Input 2

6 1
-3 -1 -2
-3 -1 1
-2 -1 2
1 4 -2
1 4 -1
1 4 1
3 1 4

Sample Output 2

INF

The area of the region the cow can reach is infinite.



Sample input:
5 6
1 2 0
0 1 1
0 2 2
-3 4 -1
-2 6 3
1 0 1
0 1 2
2 0 2
-1 -4 5
3 -2 4
1 2 4


Sample output:
13

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    N,M = map(int, sysread().split())
    verticals = []
    for i in range(N):
        verticals.append(list(map(int, sysread().split())))
    horizontals = []

    for i in range(M):
        horizontals.append(list(map(int, sysread().split())))

    verticals.sort(key=lambda x: x[2])
    horizontals.sort(key=lambda x: x[0])

    to = [[] for _ in range(N * M)]
    for xi, (a,b,c) in enumerate(verticals):
        pre = None
        for yi, (d,e,f) in enumerate(horizontals):
            if a <= d and d <= b and e <= c and c <= f:
                cur = [xi * M + yi, d]# (id, d)
                if pre == None:
                    pre = cur[:]
                    continue
                to[pre[0]].append((cur[0], cur[1] - pre[1], c))# Use Green's
                to[cur[0]].append((pre[0], - cur[1] + pre[1], c))
                pre = cur[:]


    for yi, (d,e,f) in enumerate(horizontals):
        pre = None
        for xi, (a,b,c) in enumerate(verticals):
            if a <= d and d <= b and e <= c and c <= f:
                cur = [xi * M + yi, c]# (id, c)
                if pre == None:
                    pre = cur[:]
                    continue
                to[pre[0]].append((cur[0], 0, c))
                to[cur[0]].append((pre[0], 0, c))
                pre = cur[:]


    seen = [False] * (N*M)
    INF = float('inf')
    min_sq = INF
    for i in range(N*M):
        stack = []
        goal = -1
        if not seen[i] and len(to[i]) > 0:
            heappush(stack, (0, i))# (sq, node)

        while stack:
            sq, current = heappop(stack)
            seen[current] = True
            for next, dist, y in to[current]:
                if next == i:
                    goal = 1
                    sq += dist * y
                    break
                if not seen[next]:
                    heappush(stack, (sq + dist * y, next))
        if goal == 1:
            min_sq = min(min_sq, sq)

    if min_sq == INF:
        print('INF')
    else:
        print(min_sq)


if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq
import time
start = time.time()
drc = [(-1,0),(1,0),(0,-1),(0,1)]

n, m = map(int,input().split())
tat = [list(map(int,input().split())) for i in range(n)]
yok = [list(map(int,input().split())) for i in range(m)]
xs = []
ys = []
for i in tat:
    xs.append(i[0])
    xs.append(i[1])
    ys.append(i[2])
for i in yok:
    xs.append(i[0])
    ys.append(i[1])
    ys.append(i[2])
xs = list(set(xs))
ys = list(set(ys))
dcx = dict()
dcy = dict()
for i, xi in enumerate(xs):
    dcx[xi] = i
for i, yi in enumerate(ys):
    dcy[yi] = i

xs.sort()
ys.sort()
lx = len(xs)
ly = len(ys)

sx = [xs[i]-xs[i-1] for i in range(1,lx)]
sy = [ys[i]-ys[i-1] for i in range(1,ly)]

#座標の圧縮
cps = [[0 for i in range(ly*2)] for j in range(lx*2)]
for i in tat:
    yi = dcy[i[2]]
    for j in range(dcx[i[0]],dcx[i[1]]):
        cps[2*j+1][yi*2] = -1
for i in yok:
    xi = dcx[i[0]]
    for j in range(dcy[i[1]],dcy[i[2]]):
        cps[xi*2][2*j+1] = -1
for i in range(lx-1):
    for j in range(ly-1):
        cps[2*i+1][2*j+1] = sx[i]*sy[j]
for i in range(lx):
    cps[i][-1] = -2
for j in range(ly):
    cps[-1][j] = -2


x0 = -1
y0 = -1
for i,x in enumerate(xs):
    if x > 0:
        x0 = i-1
        break
for i,y in enumerate(ys):
    if y > 0:
        y0 = i-1
        break

if x0 < 0 or y0 < 0:
    print("INF")
    exit()

ans = cps[x0*2+1][y0*2+1]
cps[x0*2+1][y0*2+1] = -1
q = queue.Queue()
q.put((x0*2+1,y0*2+1))
while not q.empty():
    x,y = q.get()
    for dx,dy in drc:
        if cps[x+dx][y+dy] == 0:
            if cps[x+dx*2][y+dy*2] > 0:
                q.put((x+dx*2,y+dy*2))
                ans += cps[x+dx*2][y+dy*2]
                cps[x+dx*2][y+dy*2] = -1
            elif cps[x+dx*2][y+dy*2] == -2:
                print("INF")
                exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq
drc = [(-1,0),(1,0),(0,-1),(0,1)]

n, m = map(int,input().split())
tat = [list(map(int,input().split())) for i in range(n)]
yok = [list(map(int,input().split())) for i in range(m)]
xs = []
ys = []
for i in tat:
    if not i[0] in xs:
        xs.append(i[0])
    if not i[1] in xs:
        xs.append(i[1])
    if not i[2] in ys:
        ys.append(i[2])
for i in yok:
    if not i[0] in xs:
        xs.append(i[0])
    if not i[1] in ys:
        ys.append(i[1])
    if not i[2] in ys:
        ys.append(i[2])

xs.sort()
ys.sort()
lx = len(xs)
ly = len(ys)

#座標の圧縮
cps = [[0 for i in range(ly*2)] for j in range(lx*2)]
for i in tat:
    yi = ys.index(i[2])
    for j in range(xs.index(i[0]),xs.index(i[1])):
        cps[2*j+1][yi*2] = -1
for i in yok:
    xi = xs.index(i[0])
    for j in range(ys.index(i[1]),ys.index(i[2])):
        cps[xi*2][2*j+1] = -1
for i in range(lx-1):
    for j in range(ly-1):
        cps[2*i+1][2*j+1] = (xs[i+1]-xs[i])*(ys[j+1]-ys[j])
for i in range(lx):
    cps[i][-1] = -2
for j in range(ly):
    cps[-1][j] = -2


x0 = -1
y0 = -1
for i,x in enumerate(xs):
    if x > 0:
        x0 = i-1
        break
for i,y in enumerate(ys):
    if y > 0:
        y0 = i-1
        break

if x0 < 0 or y0 < 0:
    print("INF")
    exit()

ans = cps[x0*2+1][y0*2+1]
'''
cps[x0*2+1][y0*2+1] = -1
q = queue.Queue()
q.put((x0*2+1,y0*2+1))
while not q.empty():
    x,y = q.get()
    for dx,dy in drc:
        if cps[x+dx][y+dy] == 0:
            if cps[x+dx*2][y+dy*2] > 0:
                q.put((x+dx*2,y+dy*2))
                ans += cps[x+dx*2][y+dy*2]
                cps[x+dx*2][y+dy*2] = -1
            elif cps[x+dx*2][y+dy*2] == -2:
                print("INF")
                exit()
'''
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
import bisect

INF = float("inf")

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

xtic = {0,-INF,INF}
ytic = {0,-INF,INF}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor_dic = defaultdict(int)
ver_dic = defaultdict(int)

for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  hor_dic[c] = (1<<b) - (1<<a)

for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  ver_dic[d] |= (1<<f) - (1<<e)

hor_dic = dict(hor_dic)
ver_dic = dict(ver_dic)

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if (hor_wall[y+1]>>x)&1:
        return False
      return True
    else:
      if (hor_wall[y]>>x)&1:
        return False
      return True
  else:
    if dx > 0:
      if (ver_wall[x+1]>>y)&1:
        return False
      return True
    else:
      if (ver_wall[x]>>y)&1:
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

hor_wall = [0 for i in range(H)]
ver_wall = [0 for i in range(W)]

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.pop()
  area += calc_area(x,y)
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if nx == 0 or ny == 0 or nx == W-1 or ny == H-1:
          print("INF")
          exit()
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from collections import deque
import bisect

INF = float("inf")

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

xtic = {0,-INF,INF}
ytic = {0,-INF,INF}

hor = []
for _ in range(N):
  a,b,c = map(int,input().split())
  hor.append((c,a,b))
  xtic.add(a)
  xtic.add(b)
  ytic.add(c)
  
ver = []
for _ in range(M):
  d,e,f = map(int,input().split())
  ver.append((d,e,f))
  xtic.add(d)
  ytic.add(e)
  ytic.add(f)

xtic = list(xtic)
ytic = list(ytic)
xtic.sort()
ytic.sort()
xdic = {xtic[i]:i+1 for i in range(len(xtic))}
ydic = {ytic[i]:i+1 for i in range(len(ytic))}

gyaku_xdic = {xdic[k]:k for k in xdic}
gyaku_ydic = {ydic[k]:k for k in ydic}

hor_dic = defaultdict(int)
ver_dic = defaultdict(int)

for c,a,b in hor:
  c,a,b = ydic[c],xdic[a],xdic[b]
  hor_dic[c] = (1<<b) - (1<<a)

for d,e,f in ver:
  d,e,f = xdic[d],ydic[e],ydic[f]
  ver_dic[d] |= (1<<f) - (1<<e)

def is_connected(x,y,dx,dy):
  if dx == 0:
    if dy > 0:
      if (hor_wall[y+1]>>x)&1:
        return False
      return True
    else:
      if (hor_wall[y]>>x)&1:
        return False
      return True
  else:
    if dx > 0:
      if (ver_wall[x+1]>>y)&1:
        return False
      return True
    else:
      if (ver_wall[x]>>y)&1:
        return False
      return True
      
def calc_area(x,y):
  X = gyaku_xdic[x+1] - gyaku_xdic[x]
  Y = gyaku_ydic[y+1] - gyaku_ydic[y]
  return X*Y

offset = [(1,0),(0,1),(-1,0),(0,-1)]
x0 = bisect.bisect(xtic,0)
y0 = bisect.bisect(ytic,0)
W,H = len(xtic)+1 ,len(ytic)+1

hor_wall = [0 for i in range(H)]
ver_wall = [0 for i in range(W)]

for k in hor_dic:
  hor_wall[k] = hor_dic[k]
for k in ver_dic:
  ver_wall[k] = ver_dic[k]

d = [[0 for i in range(W)] for j in range(H)]
d[y0][x0] = 1
q = deque([(x0,y0)])

area = 0

while q:
  x,y = q.pop()
  area += calc_area(x,y)
  for dx,dy in offset:
    nx,ny = x+dx,y+dy
    if 0<=nx<W and 0<=ny<H:
      if is_connected(x,y,dx,dy):
        if nx == 0 or ny == 0 or nx == W-1 or ny == H-1:
          print("INF")
          exit()
        if d[ny][nx] == 0:
          d[ny][nx] = 1
          q.append((nx,ny))

print(area)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    X,Y=set([0]),set([0])
    A,B,C=[0]*N,[0]*N,[0]*N
    for i in range(N):
        A[i],B[i],C[i]=map(int,input().split())
        X.add(A[i])
        X.add(B[i])
        Y.add(C[i])
    D,E,F=[0]*M,[0]*M,[0]*M
    for i in range(M):
        D[i],E[i],F[i]=map(int,input().split())
        X.add(D[i])
        Y.add(E[i])
        Y.add(F[i])
    UX=list(X)
    UY=list(Y)
    UX.sort()
    UY.sort()
    dictx,dicty={n:i*2 for i,n in enumerate(UX)},{n:i*2 for i,n in enumerate(UY)}
    LX=[UX[i//2+1]-UX[i//2] if i%2 else 0 for i in range(len(UX)*2-1)]
    LY=[UY[i//2+1]-UY[i//2] if i%2 else 0 for i in range(len(UY)*2-1)]
    c=[[0]*(len(UX)*2-1) for _ in range(len(UY)*2-1)]
    for i in range(N):
        y=dicty[C[i]]
        for x in range(dictx[A[i]],dictx[B[i]]+1):
            c[y][x]=1
    for i in range(M):
        x=dictx[D[i]]
        for y in range(dicty[E[i]],dicty[F[i]]+1):
            c[y][x]=1
    que=deque()
    used=[[0]*len(UX)*2 for _ in range(len(UY)*2)]
    dy=[1,1,-1,-1]
    dx=[1,-1,1,-1]
    for k in range(4):
        nny,nnx=dicty[0]+dy[k],dictx[0]+dx[k]
        if not 2<=nny<len(UY)*2-2 or not 2<=nnx<len(UX)*2-2:
            print('INF')
            exit()
        que.append((nny,nnx))
        used[nny][nnx]=1
    ans=0
    dy=[1,0,-1,0]
    dx=[0,1,0,-1]
    while que:
        y,x=que.popleft()
        if y%2 and x%2:
            ans+=LY[y]*LX[x]
        for k in range(4):
            ny,nx=y+dy[k],x+dx[k]
            nny,nnx=ny+dy[k],nx+dx[k]
            if c[ny][nx]==0:
                if nny<0 or nny>=len(UY)*2-1 or nnx<0 or nnx>=len(UX)*2-1:
                    print('INF')
                    exit()
                if not used[nny][nnx]:
                    que.append((nny,nnx))
                    used[nny][nnx]=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    X,Y=set([0]),set([0])
    A,B,C=[0]*N,[0]*N,[0]*N
    for i in range(N):
        A[i],B[i],C[i]=map(int,input().split())
        X.add(A[i])
        X.add(B[i])
        Y.add(C[i])
    D,E,F=[0]*M,[0]*M,[0]*M
    for i in range(M):
        D[i],E[i],F[i]=map(int,input().split())
        X.add(D[i])
        Y.add(E[i])
        Y.add(F[i])
    UX=list(X)
    UY=list(Y)
    UX.sort()
    UY.sort()
    dictx,dicty={n:i*2 for i,n in enumerate(UX)},{n:i*2 for i,n in enumerate(UY)}
    LX=[UX[i//2+1]-UX[i//2] if i%2 else 0 for i in range(len(UX)*2-1)]
    LY=[UY[i//2+1]-UY[i//2] if i%2 else 0 for i in range(len(UY)*2-1)]
    c=[[0]*len(UX)*2 for _ in range(len(UY)*2)]
    for i in range(N):
        y=dicty[C[i]]
        for x in range(dictx[A[i]],dictx[B[i]]+1):
            c[y][x]=1
    for i in range(M):
        x=dictx[D[i]]
        for y in range(dicty[E[i]],dicty[F[i]]+1):
            c[y][x]=1
    que=deque()
    used=[[0]*len(UX)*2 for _ in range(len(UY)*2)]
    dy=[1,1,-1,-1]
    dx=[1,-1,1,-1]
    for k in range(4):
        nny,nnx=dicty[0]+dy[k],dictx[0]+dx[k]
        if not 2<=nny<len(UY)*2-2 or not 2<=nnx<len(UX)*2-2:
            print('INF')
            exit()
        que.append((nny,nnx))
        used[nny][nnx]=1
    ans=0
    dy=[1,0,-1,0]
    dx=[0,1,0,-1]
    while que:
        y,x=que.popleft()
        if y%2 and x%2:
            ans+=LY[y]*LX[x]
        for k in range(4):
            ny,nx=y+dy[k],x+dx[k]
            nny,nnx=ny+dy[k],nx+dx[k]
            if c[ny][nx]==0:
                if not 2<=nny<len(UY)*2-2 or not 2<=nnx<len(UX)*2-2:
                    print('INF')
                    exit()
                if not used[nny][nnx]:
                    que.append((nny,nnx))
                    used[nny][nnx]=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**9 + 1
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    x = []; y = []
    A = []
    D = []
    for _ in range(N):
        a,b,c = LI()
        A.append((a,b,c))
        x.append(a); x.append(b)
        y.append(c); y.append(c)
    for _ in range(M):
        d,e,f = LI()
        D.append((d,e,f))
        x.append(d); x.append(d)
        y.append(e); y.append(f)

    x.append(-INF); x.append(INF); x.append(0)
    y.append(-INF); y.append(INF); y.append(0)
    x.sort(); y.sort()
    lx = len(x); ly = len(y)
    fld = [[0] * ly for _ in range(lx)]
    for a,b,c in A:
        j = bisect.bisect_left(y,c)
        for i in range(bisect.bisect_left(x,a),bisect.bisect_left(x,b)+1):
            fld[i][j] = 1
    for d,e,f in D:
        i = bisect.bisect_left(x,d)
        for j in range(bisect.bisect_left(y,e),bisect.bisect_left(y,f)+1):
            fld[i][j] = 1

    q = collections.deque()
    i = bisect.bisect_left(x,0)
    j = bisect.bisect_left(y,0)
    q.append((i,j))
    fld[i][j] = 1
    ans = 0
    while q:
        i,j = q.popleft()
        ans += (x[i+1]-x[i]) * (y[j+1]-y[j])
        for di,dj in ((0,1),(1,0),(0,-1),(-1,0)):
            if 0 <= i+di < lx-1 and 0 <= j+dj < ly-1:
                if fld[i+di][j+dj] == 0:
                    fld[i+di][j+dj] = 1
                    q.append((i+di,j+dj))
            else:
                print('INF')
                exit(0)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
ABX = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
YEF = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

# X, Y を列挙して四角をいっぱい作る
X = []
Y = []

for a, b, x in ABX:
    X.append(x)
    Y.append(a)
    Y.append(b)
for y, e, f in YEF:
    X.append(e)
    X.append(f)
    Y.append(y)

X = [-INF] + list(sorted(set(X))) + [INF, INF]
Y = [-INF] + list(sorted(set(Y))) + [INF, INF]

lines = []
for a, b, x in ABX:
    l = bisect.bisect_left(Y, min(a, b))
    r = bisect.bisect_left(Y, max(a, b))
    xi = bisect.bisect_left(X, x)
    for yi in range(l, r):
        lines.append((xi, xi, yi, yi + 1))
for y, e, f in YEF:
    l = bisect.bisect_left(X, min(e, f))
    r = bisect.bisect_left(X, max(e, f))
    yi = bisect.bisect_left(Y, y)
    for xi in range(l, r):
        lines.append((xi, xi + 1, yi, yi))
lines = set(lines)

# (0, 0) を含む場所を適当に選ぶ
xi = bisect.bisect_left(X, 0)
yi = bisect.bisect_left(Y, 0)
s = 0
seen = {(xi, yi)}
stack = [(xi, yi)]
while stack and s < INF:
    xi, yi = stack.pop()
    s += (X[xi + 1] - X[xi]) * (Y[yi + 1] - Y[yi])
    # print(X[xi], X[xi + 1], Y[yi], Y[yi + 1], (X[xi + 1] - X[xi]) * (Y[yi + 1] - Y[yi]))
    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        xj, yj = xi + dx, yi + dy
        if (xj, yj) in seen:
            continue
        if dx == 1:
            key = (xi + 1, xi + 1, yi, yi + 1)
            blocked = key in lines
        elif dx == -1:
            key = (xi, xi, yi, yi + 1)
            blocked = key in lines
        elif dy == 1:
            key = (xi, xi + 1, yi + 1, yi + 1)
            blocked = key in lines
        elif dy == -1:
            key = (xi, xi + 1, yi, yi)
            blocked = key in lines
        if blocked:
            continue
        seen.add((xj, yj))
        stack.append((xj, yj))

if s < INF:
    print(s)
else:
    print('INF')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
hlines_orig = []
Xgrid = set()
vlines_orig = []
Ygrid = set()
for _ in range(N):
    A, B, C = inpl()
    hlines_orig.append((A,B,C))
    Ygrid.add(C)
for _ in range(M):
    D, E, F = inpl()
    vlines_orig.append((D,E,F))
    Xgrid.add(D)

Xgrid = sorted(list(Xgrid))
Ygrid = sorted(list(Ygrid))
W = len(Xgrid)
H = len(Ygrid)
areas = [[(Xgrid[w+1]-Xgrid[w])*(Ygrid[h+1]-Ygrid[h]) for h in range(H-1)] for w in range(W-1)]
walled = defaultdict(bool)
dirs = {(0,1),(1,0),(-1,0),(0,-1)}
for A, B, C in hlines_orig:
    a = bisect_left(Xgrid, A)
    b = bisect_right(Xgrid, B) - 1
    c = bisect_left(Ygrid, C)
    for i in range(a, b):
        if c < H-1:
            walled[((i,c),(0,-1))] = True
        if c > 0:
            walled[((i,c-1),(0,1))] = True

for D, E, F in vlines_orig:
    d = bisect_left(Xgrid, D) 
    e = bisect_left(Ygrid, E) 
    f = bisect_right(Ygrid, F) - 1
    for i in range(e, f):
        if d < W-1:
            walled[((d,i),(-1,0))] = True
        if d > 0:
            walled[((d-1,i),(1,0))] = True

x, y = bisect_right(Xgrid, 0) - 1, bisect_right(Ygrid, 0) - 1
if x <= 0 or y <= 0 or x >= W-1 or y >= H-1:
    print('INF')
    exit()
visited = [[ False for _ in range(H-1) ] for _ in range(W-1)]
visited[x][y] = True
pool = deque([(x,y)])
ans = 0
while pool:
    x, y = pool.popleft()
    ans += areas[x][y]
    for d in dirs:
        if not walled[((x,y),d)]:
            cx, cy = x+d[0], y+d[1]
            if cx < 0 or cx >= W-1 or cy < 0 or cy >= H-1:
                print('INF')
                exit()
            elif not visited[cx][cy]:
                visited[cx][cy] = True
                pool.append((cx,cy))
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
hlines_orig = []
Xgrid = set()
vlines_orig = []
Ygrid = set()
for _ in range(N):
    A, B, C = inpl()
    hlines_orig.append((A,B,C))
    Ygrid.add(C)
for _ in range(M):
    D, E, F = inpl()
    vlines_orig.append((D,E,F))
    Xgrid.add(D)

Xgrid = sorted(list(Xgrid))
Ygrid = sorted(list(Ygrid))
W = len(Xgrid)
H = len(Ygrid)
areas = [[(Xgrid[w+1]-Xgrid[w])*(Ygrid[h+1]-Ygrid[h]) for h in range(H-1)] for w in range(W-1)]
walled = defaultdict(bool)
dirs = {(0,1),(1,0),(-1,0),(0,-1)}
for A, B, C in hlines_orig:
    a = bisect_left(Xgrid, A)
    b = bisect_right(Xgrid, B) - 1
    c = bisect_left(Ygrid, C)
    for i in range(a, b):
        if c < H-1:
            walled[((i,c),(0,-1))] = True
        if c > 0:
            walled[((i,c-1),(0,1))] = True

for D, E, F in vlines_orig:
    d = bisect_left(Ygrid, D) 
    e = bisect_left(Xgrid, E) 
    f = bisect_right(Xgrid, F) - 1
    for i in range(e, f):
        if d < W-1:
            walled[((d,i),(-1,0))] = True
        if d > 0:
            walled[((d-1,i),(1,0))] = True

x, y = bisect_right(Xgrid, 0) - 1, bisect_right(Ygrid, 0) - 1
if x <= 0 or y <= 0 or x >= W-1 or y >= H-1:
    print('INF')
    exit()
visited = [[ False for _ in range(H-1) ] for _ in range(W-1)]
visited[x][y] = True
pool = deque([(x,y)])
ans = 0
while pool:
    x, y = pool.popleft()
    ans += areas[x][y]
    for d in dirs:
        if not walled[((x,y),d)]:
            cx, cy = x+d[0], y+d[1]
            if cx < 0 or cx >= W-1 or cy < 0 or cy >= H-1:
                print('INF')
                exit()
            elif not visited[cx][cy]:
                visited[cx][cy] = True
                pool.append((cx,cy))
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
hlines_orig = []
Xgrid = set()
vlines_orig = []
Ygrid = set()
for _ in range(N):
    A, B, C = inpl()
    hlines_orig.append((A,B,C))
    Ygrid.add(C)
for _ in range(M):
    D, E, F = inpl()
    vlines_orig.append((D,E,F))
    Xgrid.add(D)

Xgrid = sorted(list(Xgrid))
Ygrid = sorted(list(Ygrid))
W = len(Xgrid)
H = len(Ygrid)
areas = [[(Xgrid[w+1]-Xgrid[w])*(Ygrid[h+1]-Ygrid[h]) for h in range(H-1)] for w in range(W-1)]
walled = defaultdict(bool)
dirs = {(0,1),(1,0),(-1,0),(0,-1)}
for A, B, C in hlines_orig:
    a = bisect_left(Xgrid, A)
    b = bisect_right(Xgrid, B) - 1
    c = bisect_left(Ygrid, C)
    for i in range(a, b):
        if c < H-1:
            walled[((i,c),(0,-1))] = True
        if c > 0:
            walled[((i,c-1),(0,1))] = True

for D, E, F in vlines_orig:
    d = bisect_left(Ygrid, D) 
    e = bisect_left(Xgrid, E) 
    f = bisect_right(Xgrid, F) - 1
    for i in range(e, f):
        if d < W-1:
            walled[((d,i),(-1,0))] = True
        if d > 0:
            walled[((d-1,i),(1,0))] = True

x, y = bisect_right(Xgrid, 0) - 1, bisect_right(Ygrid, 0) - 1
if x <= 0 or y <= 0 or x >= W-1 or y >= H-1:
    print('INF')
    exit()
else:
    x -= 1
    y -= 1
visited = [[ False for _ in range(H-1) ] for _ in range(W-1)]
visited[x][y] = True
pool = deque([(x,y)])
ans = 0
while pool:
    x, y = pool.popleft()
    ans += areas[x][y]
    for d in dirs:
        if not walled[((x,y),d)]:
            cx, cy = x+d[0], y+d[1]
            if cx < 0 or cx >= W-1 or cy < 0 or cy >= H-1:
                print('INF')
                exit()
            elif not visited[cx][cy]:
                visited[cx][cy] = True
                pool.append((cx,cy))
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
hlines_orig = []
Xgrid = set()
vlines_orig = []
Ygrid = set()
for _ in range(N):
    A, B, C = inpl()
    hlines_orig.append((A,B,C))
    Ygrid.add(C)
for _ in range(M):
    D, E, F = inpl()
    vlines_orig.append((D,E,F))
    Xgrid.add(D)

Xgrid = sorted(list(Xgrid))
Ygrid = sorted(list(Ygrid))
W = len(Xgrid)
H = len(Ygrid)
areas = [[(Xgrid[w+1]-Xgrid[w])*(Ygrid[h+1]-Ygrid[h]) for h in range(H-1)] for w in range(W-1)]
walled = defaultdict(bool)
dirs = {(0,1),(1,0),(-1,0),(0,-1)}
for A, B, C in hlines_orig:
    a = bisect_left(Xgrid, A)
    b = bisect_left(Xgrid, B)
    c = bisect_left(Ygrid, C)
    for i in range(a, b):
        if c < H-1:
            walled[((i,c),(0,-1))] = True
        if c > 0:
            walled[((i,c-1),(0,1))] = True

for D, E, F in vlines_orig:
    d = bisect_left(Ygrid, D)
    e = bisect_left(Xgrid, E)
    f = bisect_left(Xgrid, F)
    for i in range(e, f):
        if d < W-1:
            walled[((d,i),(-1,0))] = True
        if d > 0:
            walled[((d-1,i),(1,0))] = True

x, y = bisect_left(Xgrid, 0), bisect_left(Ygrid, 0)
if x == 0 or y == 0 or x >= W-1 or y >= H-1:
    print('INF')
    exit()
else:
    x -= 1
    y -= 1
visited = [[ False for _ in range(H-1) ] for _ in range(W-1)]
visited[x][y] = True
pool = deque([(x,y)])
ans = 0
while pool:
    x, y = pool.popleft()
    ans += areas[x][y]
    for d in dirs:
        if not walled[((x,y),d)]:
            cx, cy = x+d[0], y+d[1]
            if cx < 0 or cx >= W-1 or cy < 0 or cy >= H-1:
                print('INF')
                exit()
            elif not visited[cx][cy]:
                visited[cx][cy] = True
                pool.append((cx,cy))
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
hlines_orig = []
Xgrid = set()
vlines_orig = []
Ygrid = set()
for _ in range(N):
    A, B, C = inpl()
    hlines_orig.append((A,B,C))
    Ygrid.add(C)
for _ in range(M):
    D, E, F = inpl()
    vlines_orig.append((D,E,F))
    Xgrid.add(D)

Xgrid = sorted(list(Xgrid))
Ygrid = sorted(list(Ygrid))
W = len(Xgrid)
H = len(Ygrid)
areas = [[(Xgrid[w+1]-Xgrid[w])*(Ygrid[h+1]-Ygrid[h]) for h in range(H-1)] for w in range(W-1)]
walled = defaultdict(bool)
dirs = {(0,1),(1,0),(-1,0),(0,-1)}
for A, B, C in hlines_orig:
    a = bisect_left(Xgrid, A)
    b = bisect_left(Xgrid, B)
    c = bisect_left(Ygrid, C)
    for i in range(a, b):
        if c < H-1:
            walled[((i,c),(0,-1))] = True
        if c > 0:
            walled[((i,c-1),(0,1))] = True

for D, E, F in vlines_orig:
    d = bisect_left(Ygrid, D)
    e = bisect_left(Ygrid, E)
    f = bisect_left(Xgrid, F)
    for i in range(e, f):
        if d < W-1:
            walled[((d,i),(-1,0))] = True
        if d > 0:
            walled[((d-1,i),(1,0))] = True

x, y = bisect_left(Xgrid, 0), bisect_left(Ygrid, 0)
if x == 0 or y == 0 or x >= W-1 or y >= H-1:
    print('INF')
    exit()
else:
    x -= 1
    y -= 1
visited = [[ False for _ in range(H-1) ] for _ in range(W-1)]
visited[x][y] = True
pool = deque([(x,y)])
ans = 0
while pool:
    x, y = pool.popleft()
    ans += areas[x][y]
    for d in dirs:
        if not walled[((x,y),d)]:
            cx, cy = x+d[0], y+d[1]
            if cx < 0 or cx >= W-1 or cy < 0 or cy >= H-1:
                print('INF')
                exit()
            elif not visited[cx][cy]:
                visited[cx][cy] = True
                pool.append((cx,cy))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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, m = nm()
  ver = [tuple(nm()) for _ in range(n)]
  hor = [tuple(nm()) for _ in range(m)]
  xli = [0]*(2*n+m+1)
  yli = [0]*(n+2*m+1)
  for i, (a, b, c) in enumerate(ver):
    xli[i*2] = a
    xli[i*2+1] = b
    yli[i] = c
  for i, (a, b, c) in enumerate(hor):
    xli[2*n + i] = a
    yli[n + 2*i] = b
    yli[n + 2*i + 1] = c
  xli = sorted(set(xli))
  yli = sorted(set(yli))
  xdic = {x:i for i, x in enumerate(xli)}
  ydic = {x:i for i, x in enumerate(yli)}
  H = len(yli)*2 + 1
  W = len(xli)*2 + 1
  G = [[0]*W for _ in range(H)]
  for a, b, c in ver:
    a = xdic[a]; b = xdic[b]
    c = ydic[c]
    if a > b:
      a, b = b, a
    for i in range(2*a+1, 2*b+2):
      G[2*c+1][i] = 1
  for a, b, c in hor:
    a = xdic[a]
    b = ydic[b]; c = ydic[c]
    if b > c:
      b, c = c, b
    for i in range(2*b+1, 2*c+2):
      G[i][2*a+1] = 1
  # print(xli)
  # print(yli)
  # prn(G)
  q = deque()
  sx = xdic[0]*2+1; sy = ydic[0]*2+1
  G[sy][sx] = 1
  q.append((sy, sx))
  ans = 0
  '''
  while q:
    y, x = q.popleft()
    for ny, nx in ((y+1, x), (y-1, x), (y, x+1), (y, x-1)):
      if 0 <= ny < H and 0 <= nx < W and G[ny][nx] == 0:
        G[ny][nx] = -1
        q.append((ny, nx))
  '''
  for ny in range(H):
    for nx in range(W):
      if G[ny][nx] < 0:
        if ny == 0 or ny == H-1 or nx == 0 or nx == W-1:
          print('INF')
          return
        if ny % 2 == nx % 2 == 0:
          ans += (yli[ny//2] - yli[ny//2-1]) * (xli[nx//2] - xli[nx//2-1])
  print(ans)
  return

solve()