fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cstring>
  5. #define SZ(X) ((int)(X).size())
  6. using namespace std;
  7. const int MAX_N = 500000;
  8. int d[MAX_N];
  9. int tmp[MAX_N];
  10. long long dc(int L, int R) {
  11.     if(L + 1 == R) return 0;
  12.     int mm = L + (R - L) / 2;
  13.     long long answer = dc(L, mm) + dc(mm, R);
  14.     int itL = L;
  15.     int itR = mm;
  16.     int result_it = L;
  17.     while(itL < mm || itR < R) {
  18.         if(itR == R || (itL != mm && d[itL] <= d[itR])) {
  19.             answer += itR - mm;
  20.             tmp[result_it++] = d[itL++];
  21.         } else {
  22.             tmp[result_it++] = d[itR++];
  23.         }
  24.     }
  25.     memcpy(d + L, tmp + L, (R - L) * sizeof(int));
  26.     return answer;
  27. }
  28. int main() {
  29.     cin.tie(0);
  30.     ios_base::sync_with_stdio(false);
  31.     int n;
  32.     int case_num = 0;
  33.     while(cin >> n && n) {
  34.         for(int i = 0; i < n; i++) cin >> d[i];
  35.         cout << "Case #" << ++case_num << ": " << dc(0, n) << '\n';
  36.     }
  37. }
Success #stdin #stdout 0.01s 5696KB
comments (?)
stdin
copy 
5
5 4 2 1 3
stdout
copy 
Case #1: 8
https://ideone.com/Hdfe1a
language:
C++14 (gcc 8.3)
created:
5 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!