fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long merge_count(vector<long long>& b, int l, int r) {
  5.     if (r - l <= 1) return 0;
  6.     int m = (l + r) / 2;
  7.     long long inv = merge_count(b, l, m) + merge_count(b, m, r);
  8.     vector<long long> temp;
  9.     int i = l, j = m;
  10.     while (i < m && j < r) {
  11.         if (b[i] <= b[j]) temp.push_back(b[i++]);
  12.         else {
  13.             temp.push_back(b[j++]);
  14.             inv += (m - i);
  15.         }
  16.     }
  17.     while (i < m) temp.push_back(b[i++]);
  18.     while (j < r) temp.push_back(b[j++]);
  19.     for (int k = l; k < r; k++) b[k] = temp[k - l];
  20.     return inv;
  21. }
  22.  
  23. int main() {
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(NULL);
  26.  
  27.     int t;
  28.     cin >> t;
  29.     while (t--) {
  30.         int n;
  31.         cin >> n;
  32.         vector<pair<long long, long long>> v(n);
  33.         for (int i = 0; i < n; i++) cin >> v[i].first >> v[i].second;
  34.  
  35.         sort(v.begin(), v.end());
  36.  
  37.         vector<long long> b(n);
  38.         for (int i = 0; i < n; i++) b[i] = v[i].second;
  39.  
  40.         cout << merge_count(b, 0, n) << "\n";
  41.     }
  42. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
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
copy 
1
9
6
4
0
https://ideone.com/Vvv451
language:
C++ (gcc 8.3)
created:
10 hours 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!