例えば、それぞれの選手のエントリーとチームの状況が以下の図のようになっているときの、\(1\) 番の競技にエントリーしているチーム \(4\) の選手と対戦できる選手について考えてみます。

この図の赤い部分に含まれている選手が、\(1\) 番の競技にエントリーしているチーム \(4\) の選手と対戦できる選手です。 この人数を高速に求めるためには、「その競技にエントリーしている人数の合計」と、「その競技にエントリーしている同じチームの選手の人数の合計」がわかればよいです。

よって、それぞれの競技に対するエントリー人数の合計と、すべての競技\({}\times{}\)チームの組み合わせに対するエントリー人数の合計を管理できればこの問題を解くことができます。

これを二次元配列などで管理しようとすると \(10 ^ {10}\) 個の整数を管理することになり、メモリ制限や実行時間制限を超過してしまいます。 エントリーされている部分だけを連想配列などを使って管理することで、管理するべき整数の個数はたかだか \(O(N)\) 個となり、この問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <map>
using namespace std;

int main(){
    int N;
    cin >> N;

    long ans = 0;
    map<int, int> sport_count; // それぞれのスポーツにエントリーしている人数
    map<pair<int, int>, int> sport_team_count; // (スポーツ, チーム) の組に対する人数
    for (int i = 0; i < N; ++i) {
        int p, q;
        cin >> p >> q;

        // それまでにエントリーした人のうち、同じスポーツにエントリーしている別のチームの人と対戦できる
        ans += sport_count[p] - sport_team_count[{p, q}];

        // 人数を増やす
        ++sport_count[p];
        ++sport_team_count[{p, q}];
    }

    cout << ans << endl;
    return 0;
}

N = int(input())

sport_count = dict() # それぞれのスポーツにエントリーしている人数
sport_team_count = dict() # (スポーツ, チーム) の組に対する人数

ans = 0

for _ in range(N):
    p, q = map(int, input().split())

    # それまでにエントリーがなかったら、0 で埋めておく
    if p not in sport_count:
        sport_count[p] = 0
    if (p, q) not in sport_team_count:
        sport_team_count[(p, q)] = 0

    # それまでにエントリーした人のうち、同じスポーツにエントリーしている別のチームの人と対戦できる
    ans += sport_count[p] - sport_team_count[(p, q)]

    # 人数を増やす
    sport_count[p] += 1
    sport_team_count[(p, q)] += 1

print(ans)