N, M = map(int, input().split()) vlines = defaultdict(list) hlines = defaultdict(list) vticks = {0} hticks = {0} for i in range(N): A, B, C = map(int, input().split()) vlines[C].append((A, B)) hticks.add(C) vticks.update((A, B)) for i in range(M): D, E, F = map(int, input().split()) hlines[D].append((E, F)) vticks.add(D) hticks.update((E, F)) vticks = [-INF] + list(sorted(vticks)) + [INF, INF] hticks = [-INF] + list(sorted(hticks)) + [INF, INF] def up(y): return vticks[bisect.bisect_left(vticks, y) - 1] def down(y): return vticks[bisect.bisect_left(vticks, y) + 1] def left(x): return hticks[bisect.bisect_left(hticks, x) - 1] def right(x): return hticks[bisect.bisect_left(hticks, x) + 1] def area(x, y): i = bisect.bisect_left(hticks, x) width = hticks[i + 1] - hticks[i] j = bisect.bisect_left(vticks, y) height = vticks[j + 1] - vticks[j] return width * height total_area = 0 visited = set() def visit(x, y): global total_area if (x, y) in visited: return # dp("visited: x,y", x, y) a = area(x, y) total_area += a visited.add((x, y)) # visit neighbors l = left(x) if (l, y) not in visited: for a, b in vlines[x]: if a <= y < b: # blocked break else: # can move left to_visit.append((l, y)) u = up(y) if (x, u) not in visited: for a, b in hlines[y]: if a <= x < b: # blocked break else: # can move up to_visit.append((x, u)) r = right(x) if (r, y) not in visited: for a, b in vlines[r]: if a <= y < b: # blocked break else: # can move left to_visit.append((r, y)) d = down(y) if (x, d) not in visited: for a, b in hlines[d]: if a <= x < b: # blocked break else: # can move up to_visit.append((x, d)) to_visit = [(0, 0)] while to_visit: x, y = to_visit.pop() if x == INF or x == -INF or y == INF or y == -INF: print("INF") break visit(x, y) else: print(total_area)

>>> xs = [-1, 1, 2] >>> xs[bisect.bisect_left(xs, 0)] 1

vticks = {0} hticks = {0}

There are 10 candidate implementations: - Of which 8 did not match due to: Overload in function 'setitem': File: <built-in>: Line <N/A>. With argument(s): '(DictType[undefined,undefined], int64, list(undefined))': No match. - Of which 2 did not match due to: Overload in function 'impl_setitem': File: numba/typed/dictobject.py: Line 669. With argument(s): '(DictType[undefined,undefined], int64, list(undefined))': Rejected as the implementation raised a specific error: TypingError: list(undefined) as value is forbidden

# OK xticks = np.unique(np.concatenate((A, B, D, np.array([-INF, 0, INF])))) # NG yticks = np.unique(np.concatenate((E, F, C, [-INF, 0, INF])))

def add(v, w): nonlocal p nxt[p] = head[v] head[v] = p ng[p] = w p += 1

x = set() for i in range(9_000_000): x.add(i)

2510957991 Filename: f_mle.py Line # Mem usage Increment Line Contents ================================================ 24 79.117 MiB 79.117 MiB @profile 25 def main(N, M, data): ... 40 79.223 MiB 0.105 MiB xticks = np.unique(np.concatenate((E, F, C, np.array([-INF, 0, INF])))) 41 79.223 MiB 0.000 MiB yticks = np.unique(np.concatenate((A, B, D, np.array([-INF, 0, INF])))) 42 79.230 MiB 0.008 MiB width = xticks[1:] - xticks[:-1] 43 79.230 MiB 0.000 MiB height = yticks[1:] - yticks[:-1] 44 45 # compress 46 79.238 MiB 0.008 MiB A = np.searchsorted(yticks, A) ... 56 57 79.266 MiB 0.027 MiB ng_egdes = np.zeros((NUM_VERTEXES, 4), dtype=np.bool_) 87 79.484 MiB 0.000 MiB while to_visit: ... 88 79.484 MiB 0.000 MiB pos = to_visit.pop() 89 79.484 MiB 0.004 MiB y, x = divmod(pos, GRAPH_WIDTH) 90 79.484 MiB 0.012 MiB if pos in visited: ... 96 79.484 MiB 0.000 MiB total_area += width[x] * height[y] 97 79.484 MiB 0.125 MiB visited.add(pos) 98 # plan to visit neighbors 99 79.484 MiB 0.000 MiB for i in range(4): 100 79.484 MiB 0.012 MiB if not ng_egdes[pos, i]: 101 79.484 MiB 0.008 MiB to_visit.append(pos + direction[i]) 102 else: 103 79.484 MiB 0.000 MiB print(total_area)