fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. #define ll long long
  4. #define sz(a) a.size()
  5. using namespace std;
  6.  
  7. ll ans = 0;
  8.  
  9. vector <int> merge(vector <int> a, vector <int> b)
  10. {
  11.     int sz_a = sz(a), sz_b = sz(b), i = 0, j = 0;
  12.     vector <int> v;
  13.     while(i < sz_a && j < sz_b)
  14.     {
  15.         if(a[i] <= b[j])
  16.         {
  17.             v.push_back(a[i]);
  18.             ++i;
  19.         }
  20.         else
  21.         {
  22.             v.push_back(b[j]);
  23.             ++j;
  24.             ans += sz_a - i;
  25.         }
  26.     }
  27.  
  28.     while(i < sz_a) v.push_back(a[i]), ++i;
  29.     while(j < sz_b) v.push_back(b[j]), ++j;
  30.  
  31.     return v;
  32. }
  33.  
  34. vector <int> merge_sort(vector <int> v)
  35. {
  36.     int n = sz(v);
  37.     if(n == 1)
  38.         return v;
  39.  
  40.     vector <int> a(v.begin(), v.begin() + n / 2);
  41.     vector <int> b(v.begin() + n / 2, v.end());
  42.  
  43.     a = merge_sort(a);
  44.     b = merge_sort(b);
  45.  
  46.     return merge(a, b);
  47. }
  48.  
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  52.     int n; cin >> n;
  53.     vector <int> v(n);
  54.     for(int i = 0; i < n; ++i) cin >> v[i];
  55.  
  56.     v = merge_sort(v);
  57.     cout << ans << endl;
  58. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ZSirsF
language:
C++14 (gcc 8.3)
created:
24 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!