Submission #23599641

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, n) for (auto i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()

using namespace std;

using ll = long long int;
using Graph = vector<vector<int>>;

const int MOD_NUM = 1e9 + 7;

int main() {
    // Input
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    // Process
    map<int, int> a_counts;
    vector<int> counts(N);
    for (int i = N - 1; i >= 0; i--) {
        if (a_counts.find(A[i]) == a_counts.end()) {
            a_counts[A[i]] = 0;
        } else {
            a_counts[A[i]]++;
        }
        counts[i] = a_counts[A[i]];
    }

    ll ans = 0;
    rep(i, N) ans += N - i - 1 - counts[i];

    // Output
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result