Submission #31849143

---

Source Code Expand

//{{{ #include <bits/stdc++.h>
#ifndef __clang__
#include <bits/stdc++.h>
#endif
using namespace std; //}}}
const long long MOD = static_cast<int>(1e9) + 7;
//{{{TEMPLATE_BEGIN
#include <unistd.h>
using namespace std::rel_ops;
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;
typedef vector<int> vint;
#define rep(i, n)                                                              \
    for (int i = 0, i##_len = static_cast<int>(n); i < i##_len; i++)
#define all(c) begin(c), end(c)
#define perm(c)                                                                \
    sort(all(c));                                                              \
for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))
#define uniquenize(v) (v).erase(unique(all(v)), end(v))
#define cauto const auto &
#define memset(x, y) memset(x, y, sizeof(x))
#define popcount __builtin_popcount
#define gcd __gcd
inline lint bit(int x) {
    return 1LL << x;
}
template <class T>
inline int size(const T &a) {
    return (int)a.size();
}
template <class T>
inline bool chmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0;
}
template <class T>
inline int clamp(T v, T lo, T hi) {
    return (v > hi) - (v < lo);
}
template <class T>
inline bool chmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}
template <class T>
inline pair<vector<T>, char> operator*(const vector<T> &v, const char &c) {
    return make_pair(v, c);
}
template <class T>
inline istream &operator>>(istream &is, vector<T> &v) {
#ifdef ZEROKUGI
    if (v.empty()) {
        cerr << "Error L" << __LINE__ << ": vector size is zero." << endl;
        exit(EXIT_FAILURE);
    }
#endif
    for (auto &x : v)
        is >> x;
    return is;
}
template <class T>
inline ostream &operator<<(ostream &os, const pair<vector<T>, char> &v) {
    bool t = 0;
    for (const T &x : v.first) {
        if (t)
            os << v.second;
        os << x;
        t = 1;
    }
    return os;
}
template <class T>
inline ostream &operator<<(ostream &os, vector<T> &v) {
    return os << v * ' ';
}
struct before_main {
    before_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} __before_main;
//}}}TEMPLATE_END

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    vector<lint> cnt(200000+1);
    for(int x: a) {
        cnt[x]++;
    }

    lint l = 0;
    lint r = n;
    lint c = 0;
    lint ans = 0;
    for(int i = 1; i <= 200000; i++) {
        // move
        l += c;
        c = cnt[i];
        r -= c;
        ans += l*c*r;
    }
    cout << ans << endl;
}

Submission Info

Judge Result