fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long ll;
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8. int a[100005];
  9.  
  10. // ketika masuk ke function merge
  11. // bagian kiri sudah sorted
  12. // bagian kanan sudah sorted
  13. ll merge(ll l, ll m, ll r) {
  14.     // menghitung panjang dari subarray kiri dan kanan
  15.     int n1 = m - l + 1, n2 = r - m; 
  16.  
  17.     // untuk mengambil nilai subarray kiri dan kanan
  18.     int left[n1], right[n2];
  19.     for (int i = 0; i < n1; i++) {
  20.         left[i] = a[i + l];
  21.     }
  22.     for (int i = 0; i < n2; i++) {
  23.         right[i] = a[m + 1 + i];
  24.     }
  25.  
  26.     ll res = 0;
  27.     int i = 0, j = 0, k = l;
  28.     while (i < n1 && j < n2) {
  29.         // menaruh nilai yang paling kecil antara 2 bilangan yang ditunjuk ke dalam array
  30.         if (left[i] <= right[j]) {
  31.             a[k] = left[i];
  32.             k++, i++;
  33.         } else {
  34.             a[k] = right[j];
  35.             k++, j++;
  36.             res += n1 - i;
  37.         }
  38.     }
  39.     // menaruh sisa array di subkiri/kanan ke dalam array asli
  40.     while (i < n1) {
  41.         a[k++] = left[i++];
  42.         k++, i++;
  43.     }
  44.     while (j < n2) {
  45.         a[k] = right[j];
  46.         k++, j++;
  47.     }
  48.     return res;
  49. }
  50.  
  51. ll dnc(int l, int r) {
  52.     ll res = 0;
  53.     if (l < r) {
  54.         int m = (l + r) / 2;
  55.         res += dnc(l, m);
  56.         res += dnc(m + 1, r);
  57.         res += merge(l, m, r);
  58.     }
  59.     return res;
  60. }
  61.  
  62. int main() {
  63.     cin.tie(0) -> sync_with_stdio(false), cout.tie(0);
  64.     cin >> n;
  65.     for (int i = 0; i < n; i++) {
  66.         cin >> a[i];
  67.     }
  68.     ll ans = dnc(0, n - 1);
  69.     cout << ans << '\n';
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Db478q
language:
C++ (gcc 8.3)
created:
1 day 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!