Educational Codeforces Round 161 (Rated for Div. 2) 1922B. Forming Triangles Solution

 

 Problem Link :  https://codeforces.com/contest/1922/problem/B

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. int32_t main() {
5. ios_base::sync_with_stdio(0);
6. cin.tie(0);
7. int t;
8. cin >> t;
9. while (t--) {
10. int n ; cin >> n ;
11. vector<int>a(n) ;
12. map<int,int>mp ;
13. for ( int i = 0 ; i < n ; i++){
14. cin >> a[i] ;
15. mp[a[i]]++ ;
16. }
17. sort(a.begin(),a.end()) ;
18. long long ans = 0 ;
19. for (auto [x,y] : mp ){
20. ans += ( 1LL * y * ( y - 1) * ( y - 2) ) / 6 ;
21. int index = lower_bound(a.begin(),a.end(),x) - a.begin() ;
22. ans += ( 1ll * ( y * ( y - 1 )) / 2) * index ;
23. }
24. cout << ans << '\n' ;
25. }
26. return 0 ;
27. }