Overview

Given \(N\) points (flower beds), for each point, we remove it and compute the “number of distinct \(X\) coordinates \(C'_x\)” and “number of distinct \(Y\) coordinates \(C'_y\)” among the remaining points, then calculate the number of empty cells (\(C'_x \times C'_y - (N-1)\)) for each point.

Analysis

To find the number of empty cells, we need to efficiently determine \(C'_x\) and \(C'_y\) after removing a specific point \((X_i, Y_i)\).

1. Naive Approach and Its Limitations

For each \(i\), if we re-examine all remaining \(N-1\) points to count \(C'_x\) and \(C'_y\), it takes \(O(N)\) time per point. The overall complexity becomes \(O(N^2)\), which is too slow under the constraint \(N = 2 \times 10^5\).

2. Conditions Under Which the Coordinate Count Changes

Let \(C_x\) be the number of distinct \(X\) coordinates in the original state. When point \(i\) is removed, \(C'_x\) can only be one of two values: - If no other flower bed shares the same \(X\) coordinate as \(X_i\): The value \(X_i\) disappears from the set of coordinates, so \(C'_x = C_x - 1\). - If other flower beds with the same \(X\) coordinate as \(X_i\) exist: The value \(X_i\) still remains in the set, so \(C'_x = C_x\).

The same logic applies to \(Y\) coordinates. Therefore, if we precompute how many times each \(X\) coordinate and \(Y\) coordinate appears, we can determine \(C'_x\) and \(C'_y\) for each removed point in constant time \(O(1)\).

Algorithm

1. Scan all flower bed coordinates and prepare the following information:
   • An associative array (dictionary) x_counts recording the occurrence count of each \(X\) coordinate
   • An associative array (dictionary) y_counts recording the occurrence count of each \(Y\) coordinate
   • The original number of distinct \(X\) coordinates \(C_x\) (the number of entries in x_counts)
   • The original number of distinct \(Y\) coordinates \(C_y\) (the number of entries in y_counts)
2. For each flower bed \(i = 1, \ldots, N\), compute the following in order:
   • If x_counts[X_i] == 1, then \(C'_x = C_x - 1\); otherwise \(C'_x = C_x\)
   • If y_counts[Y_i] == 1, then \(C'_y = C_y - 1\); otherwise \(C'_y = C_y\)
   • Output the number of empty cells: \(C'_x \times C'_y - (N-1)\).

Complexity

• Time complexity: \(O(N)\)
  • Counting coordinates takes \(O(N)\), and determining each point takes \(O(N)\). Associative array operations are \(O(1)\) on average.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the list holding coordinate data and the associative arrays recording occurrence counts.

Implementation Notes

• In Python, reading all input at once using sys.stdin.read().split() is faster.

• Instead of printing one line at a time with print, storing results in a list and outputting them all at once with '\n'.join() reduces I/O bottleneck.

• Since coordinate values can be large (up to \(10^9\)), we use a hash map (dict) instead of an array to manage occurrence counts.

  Source Code

import sys

def solve():
    # 入力を標準入力から全て読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    points = []
    x_counts = {}
    y_counts = {}
    
    idx = 1
    for _ in range(n):
        x = int(input_data[idx])
        y = int(input_data[idx+1])
        points.append((x, y))
        
        # X座標の出現回数をカウント
        x_counts[x] = x_counts.get(x, 0) + 1
        # Y座標の出現回数をカウント
        y_counts[y] = y_counts.get(y, 0) + 1
        
        idx += 2
        
    # 元の配置図における相異なるX座標とY座標の個数
    cx_total = len(x_counts)
    cy_total = len(y_counts)
    
    results = []
    for x, y in points:
        # 花壇iを除いたときの相異なるX座標の個数 Cx'
        # その花壇のX座標が1回しか現れていなければ、除いた後は個数が1減る
        if x_counts[x] == 1:
            cx_prime = cx_total - 1
        else:
            cx_prime = cx_total
            
        # 花壇iを除いたときの相異なるY座標の個数 Cy'
        # その花壇のY座標が1回しか現れていなければ、除いた後は個数が1減る
        if y_counts[y] == 1:
            cy_prime = cy_total - 1
        else:
            cy_prime = cy_total
            
        # 空きセル数 = セルの総数 - 花壇の数
        # 除いた後の花壇の数は N-1
        empty_cells = cx_prime * cy_prime - (n - 1)
        results.append(str(empty_cells))
    
    # 結果を一括で出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.