fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int a[200000];
  4. long long bit[200000];
  5. unordered_map<int,int> mp;
  6. set<int> st;
  7. int n;
  8. void put(int i){
  9. 	while(i<n+2){
  10. 		bit[i]++;
  11. 		i+=(i&-i);
  12. 	}
  13. }
  14. long long get(int i){
  15. 	long long sm=0;
  16. 	while(i>0){
  17. 		sm+=bit[i];
  18. 		i-=(i&-i);
  19. 	}
  20. 	return sm;
  21. }
  22. int main(){
  23. 	ios_base::sync_with_stdio(0);
  24. 	cin.tie(0);
  25. 	int t;
  26. 	cin>>t;
  27. 	for(int i=0;i<t;i++){
  28. 		cin>>n;
  29. 		mp.clear();
  30. 		st.clear();
  31. 		for(int j=0;j<n+2;j++){
  32. 			bit[j]=0;
  33. 		}
  34. 		for(int j=0;j<n;j++){
  35. 			cin>>a[j];
  36. 			st.insert(a[j]);
  37.  
  38. 		}
  39.  
  40. 		//compress data!
  41. 		int in=n+1;
  42. 		for(set<int>::iterator it=st.begin();it!=st.end();it++){
  43. 			mp[*it]=in;
  44. 			in--;
  45. 		}
  46. 		long long sum=0;
  47. 		for(int j=0;j<n;j++){
  48. 			sum+=get(mp[a[j]]);
  49. 			put(mp[a[j]]+1);
  50. 		}
  51. 		cout<<sum<<"\n";
  52. 	}
  53. 	return 0;
  54. }
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
2
5
1 1 1 2 2
5
2 1 3 1 2
stdout
copy 
0
4
https://ideone.com/3n1BPR
language:
C++14 (clang 8.0)
created:
6 years 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!