Advertisement
Guest User

Untitled

a guest
Dec 16th, 2017
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector <longint> a, b;
  7. int count = 0;
  8.  
  9. void mergeSort(int l, int r){
  10.     if (l >= r) {
  11.         return;
  12.     }
  13.     int m = (l + r + 1)/2;
  14.     mergeSort(l, m - 1);
  15.     mergeSort(m, r);
  16.    
  17.    
  18.     int i = l;
  19.     int j = m;
  20.     int k = l;
  21.     while (k <= r){
  22.            
  23.         if (i < m && (j > r || a[i] <= a[j])){
  24.             b[k] = a[i];
  25.             ++i;
  26.             ++k;
  27.         } else {
  28.             b[k] = a[j];
  29.             ++j;
  30.             ++k;
  31.             count += m - i;
  32.         }
  33.     }
  34.        
  35.     for (int x = l; x <= r; ++x) {
  36.         a[x] = b[x];
  37.     }
  38. return;
  39.    
  40. }
  41.  
  42. int main() {
  43.     int n;
  44.     int L;
  45.     cin >> n >> L;
  46.     a.resize(n);
  47.     b.resize(n);
  48.     double w;
  49.     for (int i = 0; i < n; ++i){
  50.         cin >> w;
  51.         a[i] = L*w + i;
  52.     }
  53.     mergeSort(0, a.size() - 1);
  54.     cout << count << "\n";
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement