fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 6e4 + 5; 
  11. const int MAX_A = 6e4 + 5; 
  12.  
  13. int n;  
  14. int a[N], ft[MAX_A]; 
  15.  
  16. void update(int i, int val) {
  17. 	for (; i > 0; i -= i & (-i)) ft[i] += val;  
  18. }
  19.  
  20. int get(int i) {
  21. 	int ans = 0;   
  22. 	for (; i < MAX_A; i += i & (-i)) ans += ft[i];  
  23. 	return ans;  
  24. }
  25.  
  26. int main() {
  27. 	ios::sync_with_stdio(0); cin.tie(0);  	
  28. 	cin >> n;  
  29. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  30.  
  31. 	ll ans = 0;  
  32. 	// for (int i = 1; i <= n; i++) {
  33. 	// 	int cnt = 0;   
  34. 	// 	for (int j = i - 1; j >= 1; j--) {
  35. 	// 		if (a[j] > a[i]) cnt++; 
  36. 	// 	}
  37. 	// 	ans += cnt;  
  38. 	// }
  39.  
  40. 	for (int i = 1; i <= n; i++) {
  41. 		// đếm bao nhiêu thằng j < i mà a[j] thuộc đoạn [a[i] + 1, MAX_A - 1]
  42. 		int cnt = get(a[i] + 1); 
  43. 		ans += cnt;   
  44. 		update(a[i], 1); 
  45. 	}
  46.  
  47. 	cout << ans << '\n'; 
  48. }
  49.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
3
3
1
2
stdout 
2
https://ideone.com/t16pJ5
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!