fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #define SZ(X) ((int)(X).size())
  5. using namespace std;
  6. long long dc(vector<int> d) {
  7.     int mi = *min_element(d.begin(), d.end());
  8.     int ma = *max_element(d.begin(), d.end());
  9.     if(mi == ma) return 0;
  10.     int mid = mi + (ma - mi) / 2; 
  11.     vector<int> a, b;
  12.     int now = 0;
  13.     long long ret = 0;
  14.     for(int i = 0; i < SZ(d); i++) {
  15.         if(d[i] <= mid) {
  16.             a.push_back(d[i]);
  17.             ret += SZ(b);
  18.         } else  b.push_back(d[i]);
  19.     }
  20.     cout << ret << endl; 
  21.     return ret + dc(a) + dc(b);
  22. }
  23. int main() {
  24.     int n;
  25.     cin >> n;
  26.     vector<int> d(n);
  27.     for(int &x: d) cin >> x;
  28.     cout << dc(d) << '\n';
  29. }
Success #stdin #stdout 0s 5256KB
comments (?)
stdin
copy 
5
3 -4 3 -1 2
stdout
copy 
3
0
2
5
https://ideone.com/IGoIj2
language:
C++14 (gcc 8.3)
created:
2 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!