fork download
copy 
  1. #include <cstdio>
  2.  
  3. long long res;
  4.  
  5. int N;
  6.  
  7. int A[100003];
  8. int B[100003];
  9.  
  10. void get_inversion(int s, int e) {
  11.     if (s == e) {
  12.         return;
  13.     }
  14.     if (e - s == 1) {
  15.         if (A[s] > A[e]) {
  16.             int t = A[s];
  17.             A[s] = A[e];
  18.             A[e] = t;
  19.             res ++;
  20.         }
  21.         return;
  22.     }
  23.  
  24.     int m = (s + e) / 2;
  25.     get_inversion(s, m);
  26.     get_inversion(m + 1, e);
  27.  
  28.     int l = s;
  29.     int r = m + 1;
  30.     int p = s;
  31.     while (l <= m && r <= e) {
  32.         if (A[l] < A[r]) {
  33.             B[p ++] = A[l ++];
  34.         } else {
  35.             B[p ++] = A[r ++];
  36.             res += (m + 1 - l);
  37.         }
  38.     }
  39.     while (l <= m) {
  40.         B[p ++] = A[l ++];
  41.     }
  42.     while (r <= e) {
  43.         B[p ++] = A[r ++];
  44.     }
  45.  
  46.     for (int i = s; i <= e; i ++) {
  47.         A[i] = B[i];
  48.     }
  49. }
  50.  
  51. int main() {
  52.     scanf("%d", &N);
  53.  
  54.     for (int i = 0; i < N; i ++) {
  55.         scanf("%d", &A[i]);
  56.     }
  57.  
  58.     get_inversion(0, N - 1);
  59.     printf("%lld\n", res);
  60.     return 0;
  61. }
Success #stdin #stdout 0s 4252KB
comments (?)
stdin
copy 
5
5 3 2 4 1
stdout
copy 
8
https://ideone.com/0jDnfg
language:
C++14 (gcc 8.3)
created:
7 years 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!