Overview

When removing each flower bed one at a time, we efficiently compute the number of empty cells for all flower beds, where the empty cells equal “number of distinct \(X\) values” × “number of distinct \(Y\) values” of the remaining points minus the number of remaining points.

Analysis

The total number of cells in the arrangement is determined by “the number of distinct \(X\) coordinates used” \(C_x\) and “the number of distinct \(Y\) coordinates used” \(C_y\) as \(C_x \times C_y\). Therefore, after removing one flower bed, what we need to know is:

• Does removing it reduce the number of distinct \(X\) values? (Is that \(X\) value still present in the remaining points?)
• Does removing it reduce the number of distinct \(Y\) values? (Is that \(Y\) value still present in the remaining points?)

These are the only two things we need to check.

If we naively construct “the set without flower bed \(i\)” for each \(i\) and count the distinct \(X\) and \(Y\) values each time, it takes \(O(N)\) per query, resulting in \(O(N^2)\) overall, which is too slow for \(N \le 2 \times 10^5\) (TLE).

The key insight here is:

• When removing flower bed \(i\), if \(X_i\) appears only in that flower bed (frequency is 1), then \(C'_x = C_x - 1\); otherwise \(C'_x = C_x\)
• Similarly for \(Y\): if the frequency of \(Y_i\) is 1, then \(C'_y = C_y - 1\); otherwise it stays the same

In other words, as long as we know the frequency (occurrence count) of each coordinate value, the answer for each \(i\) can be computed in \(O(1)\).

Simple example: - If there are 3 distinct \(X\) values and 4 distinct \(Y\) values, the original total number of cells is \(12\) - If we remove a point whose \(X\) value is unique, the number of distinct \(X\) values decreases to 2 (otherwise it stays at 3) - Similarly determine the change in the number of distinct \(Y\) values, and simply output \(C'_x \times C'_y - (N-1)\)

Algorithm

1. For all flower beds, count the frequency of \(X\) values cntx[x] and \(Y\) values cnty[y] using a dictionary (associative array).
2. Compute \(C_x = |\{X_i\}|\) and \(C_y = |\{Y_i\}|\) as the number of keys in each dictionary.
3. For each flower bed \(i\), do the following:
   • dx = 1 if cntx[X_i] == 1 (removing it eliminates that \(X\) value), otherwise dx = 0
   • dy = 1 if cnty[Y_i] == 1, otherwise dy = 0
   • \(C'_x = C_x - dx\), \(C'_y = C_y - dy\)
   • The answer is \(C'_x \times C'_y - (N - 1)\)
4. Output the above for \(i=1..N\).

Complexity

• Time complexity: \(O(N)\) (frequency counting is \(O(N)\), computation for each \(i\) is \(O(1)\), totaling \(O(N)\))
• Space complexity: \(O(N)\) (the coordinate arrays and dictionaries hold at most about \(N\) elements)

Implementation Notes

• “Whether the number of distinct values decreases upon removal” can be determined solely by “whether the frequency of that value is 1.”

• Since coordinate values range from \(-10^9\) to \(10^9\), which is large, we should not manage them directly with arrays but instead count them using a dictionary (e.g., Python’s dict).

• For output, using "\n".join(...) to write everything at once is faster.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    xs = [0] * N
    ys = [0] * N

    cntx = {}
    cnty = {}

    for i in range(N):
        x, y = map(int, input().split())
        xs[i] = x
        ys[i] = y
        cntx[x] = cntx.get(x, 0) + 1
        cnty[y] = cnty.get(y, 0) + 1

    Cx = len(cntx)
    Cy = len(cnty)

    out = []
    for i in range(N):
        dx = 1 if cntx[xs[i]] == 1 else 0
        dy = 1 if cnty[ys[i]] == 1 else 0
        Cx2 = Cx - dx
        Cy2 = Cy - dy
        out.append(str(Cx2 * Cy2 - (N - 1)))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.