fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int> ord2;
  4. int f(int l, int r){
  5. int ans = 0;
  6. if(l + 1 >= r) return ans;
  7. int mid = (l + r) / 2;
  8. ans += f(l, mid) + f(mid, r);
  9. int i = l, j = mid;
  10. while(i < mid && j < r){
  11. if(ord2[i] < ord2[j]){
  12. i++;
  13. }else{
  14. ans += mid - i;
  15. j++;
  16.  
  17. }
  18. }
  19. inplace_merge(ord2.begin()+l, ord2.begin()+mid, ord2.begin()+r);
  20. return ans;
  21.  
  22. }
  23. void solve(){
  24. int n;
  25. cin >> n;
  26. vector<pair<int, int>> vec;
  27. for(int i = 0; i < n; i++){
  28. int a, b;
  29. cin >> a >> b;
  30. vec.push_back({b, a});
  31. }
  32. sort(vec.begin(), vec.end(), greater<pair<int, int>>());
  33. vector<pair<int, int>> ord;
  34. for(int i = 0; i < n; i++){
  35. ord.push_back({vec[i].second, i + 1});
  36.  
  37. }
  38. sort(ord.begin(), ord.end(), greater<pair<int, int>>());
  39. ord2.clear();
  40. for(int i = 0; i < n; i++){
  41. ord2.push_back(ord[i].second);
  42. }
  43.  
  44. cout << f(0, n) << endl;
  45. }
  46. int main() {
  47. int t;
  48. cin >> t;
  49. while(t--){
  50. solve();
  51. }
  52. }
Success #stdin #stdout 0.01s 5284KB
stdin
5
2
2 3
1 4
6
2 6
3 9
4 5
1 8
7 10
-2 100
4
-10 10
-5 5
-12 12
-13 13
5
-4 9
-2 5
3 4
6 7
8 10
4
1 2
3 4
5 6
7 8
stdout
1
9
6
4
0