fork download
copy 
  1. /*
  2. ==> Don't stop when you're tired, stop when you're done.
  3. --> @author: MIDORIYA_
  4. */
  5. //*==============================================================
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef double db;
  10. typedef long double ld;
  11. typedef pair<int, int> pii;
  12. typedef vector<int> vi;
  13. typedef vector<ll> vll;
  14. typedef vector<db> vd;
  15. typedef vector<ld> vld;
  16. typedef vector<bool> vb;
  17. typedef vector<vector<ll>> vvl;
  18. typedef vector<pii> vii;
  19. typedef set<int> si;
  20. typedef set<ll> sl;
  21. #define pb push_back
  22. #define all(x) x.begin(), x.end()
  23. #define rall(x) x.rbegin(), x.rend()
  24. #define Green true
  25. #define Red false
  26. #define endl '\n'
  27. const ll mod = 1'000'000'007;
  28. #define INF 2'000'000'000
  29. #define time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << endl;
  30. //*===================>>>Fast-IO-Functions<<<=================
  31. void fastIO()
  32. {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(nullptr);
  35.     cout.tie(nullptr);
  36. }
  37. //*===================>>>File-IO-Functions<<<=================
  38. void fileIO()
  39. {
  40. #ifndef ONLINE_JUDGE
  41.     freopen("in.txt", "r", stdin);
  42.     freopen("out.txt", "w", stdout);
  43. #endif
  44. }
  45. //*===================>>>ONE-FOR-ALL-Function<<<==============
  46. ll nCr(ll n, ll r)
  47. {
  48.     if (r > n)
  49.         return 0;
  50.     ll p = 1, k = 1;
  51.     if (n - r < r)
  52.         r = n - r;
  53.     if (n < 1)
  54.         return 0;
  55.     while (r)
  56.     {
  57.         p *= n, k *= r;
  58.         ll m = __gcd(p, k);
  59.         p /= m, k /= m, n--, r--;
  60.     }
  61.     return p;
  62. }
  63.  
  64. void OneForAll()
  65. {
  66.     int n;
  67.     cin >> n;
  68.  
  69.     map<int, int> numOfLen;
  70.     for (int i = 0; i < n; i++)
  71.     {
  72.         int x;
  73.         cin >> x;
  74.         numOfLen[x]++;
  75.     }
  76.  
  77.     ll res = 0;
  78.     ll sum = 0;
  79.     for(auto & it : numOfLen)
  80.     {
  81.         ll cnt = it.second;
  82.         if(cnt >= 3)
  83.         {
  84.             res += nCr(cnt, 3);
  85.         }
  86.         if(cnt >= 2)
  87.         {
  88.             res += nCr(cnt, 2) * sum;
  89.         }
  90.         sum += cnt;
  91.     }
  92.  
  93.     cout << res << endl;
  94. }
  95.  
  96. int main()
  97. { 
  98.     fastIO();
  99.     fileIO();
  100.  
  101.     ll tc = 1;
  102.     cin >> tc;
  103.     while (tc--)
  104.     {
  105.         OneForAll();
  106.     }
  107.     time;
  108.     return 0;
  109. }
Success #stdin #stdout #stderr 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time Taken: 0.004476 Secs
https://ideone.com/vinF0d
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!