Advertisement
Josif_tepe

Untitled

Jan 26th, 2023
871
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <set>
  6. #include <cstring>
  7. #include <fstream>
  8. using namespace std;
  9.  
  10.  
  11. using namespace std;
  12. long long my_merge(vector<int>&v, vector<int> &tmp, int L, int mid, int R) {
  13.     int i = L, j = mid;
  14.     int idx = L;
  15.     long long inversions = 0;
  16.     while(i <= mid - 1 and j <= R) {
  17.         if(v[i] <= v[j]) {
  18.             tmp[idx++] = v[i++];
  19.         }
  20.         else {
  21.             tmp[idx++] = v[j++];
  22.             inversions += mid - i;
  23.         }
  24.     }
  25.    
  26.     while(i <= mid - 1) {
  27.         tmp[idx++] = v[i++];
  28.     }
  29.     while(j <= R) {
  30.         tmp[idx++] = v[j++];
  31.     }
  32.     for(int id = L; id <= R; id++) {
  33.         v[id] = tmp[id];
  34.     }
  35.     return inversions;
  36. }
  37. long long merge_sort(vector<int> &v, vector<int> &tmp, int L, int R) {
  38.     int mid = (L + R) / 2;
  39.     long long inversions = 0;
  40.    
  41.     if(R > L) {
  42.         inversions += merge_sort(v, tmp, L, mid);
  43.         inversions += merge_sort(v, tmp, mid + 1, R);
  44.         inversions += my_merge(v, tmp, L, mid + 1, R);
  45.        
  46.     }
  47.     return inversions;
  48. }
  49. int main()
  50. {
  51.     int n;
  52.     cin >> n;
  53.    
  54.     vector<int> v(n);
  55.      
  56.     for(int i = 0; i < n; i++) {
  57.         cin >> v[i];
  58.     }
  59.     vector<int> tmp(n);
  60.     cout << merge_sort(v, tmp, 0, n - 1) << endl;
  61.     return 0;
  62. }
  63.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement