fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. vector<int> ord; 
  5.  
  6. int f(int l, int r){
  7.     int ans = 0;
  8.  
  9. 	if(l + 1 >= r) return 0;
  10. 	int mid = (l + r) / 2;
  11. 	ans += f(l, mid) + f(mid, r);
  12. 	int i = l, j = mid;
  13. 	while(i < mid && j < r){
  14. 		if(ord[i] < ord[j]){
  15. 			i++;
  16. 		}else{
  17. 			ans += mid - i; 
  18. 			j++;
  19. 		}
  20. 	}
  21. 	inplace_merge(ord.begin() + l, ord.begin() + mid, ord.begin() + r);
  22. 	return ans; 
  23. }
  24. signed main(){
  25. 	cin >> n;
  26. 	map<char, queue<int>> mp;
  27. 	string s;
  28. 	cin >> s;
  29. 	string s2 = s;
  30. 	reverse(s2.begin(), s2.end());
  31. 	for(int i = 0; i < n; i++){
  32. 		mp[s2[i]].push(i + 1);
  33. 	}
  34. 	for(int i = 0; i < n; i++){
  35. 		ord.push_back(mp[s[i]].front());
  36. 		mp[s[i]].pop();
  37. 	}
  38. 	cout << f(0, n) << endl; 
  39.  
  40. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
9
icpcsguru
stdout
copy 
30
https://ideone.com/z1Iatl
language:
C++14 (gcc 8.3)
created:
2 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!