Overview

Given the competition numbers and team numbers of \(N\) players, find the number of pairs who are entered in the same competition and belong to different teams.

Analysis

First, if we naively try all pairs, there are up to \(\frac{N(N-1)}{2}\) combinations, and since \(N\) can be up to \(2 \times 10^5\), this cannot be computed within the time limit (TLE).

The key observation is that a match is valid when players are “entered in the same competition” and “belong to different teams”. Therefore, it is efficient to group players by competition number and count the number of pairs from different teams within each competition.

For example, consider a competition where the teams and their member counts are as follows: - Team A: 2 people - Team B: 3 people - Team C: 1 person

The number of combinations choosing from different teams is: $\( (2 \times 3) + (2 \times 1) + (3 \times 1) = 6 + 2 + 3 = 11 \)$

This kind of calculation can be computed using the formula where \(S\) is the total number of people across all teams and \(c_i\) is the number of people in each team: $\( \text{number of combinations} = \frac{S^2 - \sum c_i^2}{2} \)\( This can be understood as subtracting the combinations within the same team (\)c_i^2$) and dividing by 2 to ignore ordering.

Using this formula, each competition can be computed in \(O(T)\) (where \(T\) is the number of teams in that competition), which is sufficiently fast overall.

Algorithm

1. Aggregate each player’s information in the form “competition number → team number → count”.
2. For each competition, obtain the list of member counts per team participating in that competition.
3. Using the formula \(\frac{S^2 - \sum c_i^2}{2}\), compute the number of valid pairs for that competition.
4. Compute this for all competitions and sum them up.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• sys.stdin.read is used to efficiently read player information.
• By using defaultdict, we can count without checking for key existence in advance.
• For each competition, we aggregate the number of people per team and apply the above formula for efficient computation.

## Source Code

```python
from collections import defaultdict
import sys

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

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

# 競技ごとに、チームごとの人数をカウント
competition_teams = defaultdict(lambda: defaultdict(int))

for p, q in players:
    competition_teams[p][q] += 1

total_combinations = 0

# 各競技について
for teams in competition_teams.values():
    team_counts = list(teams.values())
    # ある競技での総対戦数 = Σ (count[i] * count[j]) for i < j
    # これは (sum)^2 - sum of squares を使って高速に計算できる
    total = sum(team_counts)
    square_sum = sum(c * c for c in team_counts)
    combinations = (total * total - square_sum) // 2
    total_combinations += combinations

print(total_combinations)

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