Overview

Given the coordinates of \(N\) flower beds, find the number of empty cells in the layout diagram when each flower bed is removed one at a time.

Analysis

In this problem, we need to create a “layout diagram” after removing each flower bed. The layout diagram is based on a grid of size \(C_x \times C_y\), determined by the number of distinct \(X\) coordinates and \(Y\) coordinates that appear.

A naive approach would be to count the distinct \(X\) and \(Y\) values among the \(N-1\) remaining points each time to compute the grid size, but this takes \(O(N)\) per point, resulting in \(O(N^2)\) overall, which is too slow for the constraint \(N \leq 2 \times 10^5\).

Instead, if we precompute the occurrence count of each \(X\) and \(Y\) coordinate across all points, we can determine in \(O(1)\) whether removing a given point causes its \(X\) or \(Y\) coordinate to disappear (i.e., whether the grid size shrinks). Specifically, if a coordinate is contained in only one point, removing that point decreases the number of distinct values for that coordinate by 1.

By performing this preprocessing, the overall time complexity can be kept to \(O(N \log N)\) (with sorting being the bottleneck).

Algorithm

1. Collect the \(X\) and \(Y\) coordinates of all points, remove duplicates, and sort them to obtain unique lists.
2. Convert each coordinate value to its index in the corresponding list, and record the occurrence count for each index.
3. Compute the overall grid size \(C_x \times C_y\) and calculate the number of empty cells as \(C_x \cdot C_y - N\).
4. For each point, do the following:
   • Check the occurrence count corresponding to that point’s \(X\) and \(Y\) indices. If the count is 1, determine that the size along that axis decreases by 1.
   • Compute the new number of empty cells from the new grid size and output it.

Complexity

• Time complexity: \(O(N \log N)\) (mainly due to sorting the coordinates)
• Space complexity: \(O(N)\)

Implementation Notes

• By performing coordinate compression, we avoid dealing with unnecessarily large coordinate values and can manage everything using index-based representation.

• By managing occurrence counts with a defaultdict, the impact of each point can be retrieved efficiently.

• The effect of removing each point depends only on “whether there exists a coordinate that belongs to only that point,” so we only need to check that.

  Source Code

import sys
from collections import defaultdict

input = sys.stdin.read
data = input().split()

N = int(data[0])
XY = [(int(data[2*i+1]), int(data[2*i+2])) for i in range(N)]

Xs = [x for x, y in XY]
Ys = [y for x, y in XY]

sorted_X = sorted(set(Xs))
sorted_Y = sorted(set(Ys))

X_to_idx = {x: i for i, x in enumerate(sorted_X)}
Y_to_idx = {y: i for i, y in enumerate(sorted_Y)}

# 各x, yの出現回数
count_x = defaultdict(int)
count_y = defaultdict(int)

for x, y in XY:
    count_x[X_to_idx[x]] += 1
    count_y[Y_to_idx[y]] += 1

Cx = len(sorted_X)
Cy = len(sorted_Y)

total_cells = Cx * Cy
empty_cells_all = total_cells - N

results = []

for x, y in XY:
    idx_x = X_to_idx[x]
    idx_y = Y_to_idx[y]
    
    # x座標の種類数の変化
    if count_x[idx_x] == 1:
        new_Cx = Cx - 1
    else:
        new_Cx = Cx
        
    # y座標の種類数の変化
    if count_y[idx_y] == 1:
        new_Cy = Cy - 1
    else:
        new_Cy = Cy
    
    new_total_cells = new_Cx * new_Cy
    new_empty_cells = new_total_cells - (N - 1)
    results.append(new_empty_cells)

print('\n'.join(map(str, results)))

This editorial was generated by qwen3-coder-480b.