fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int t[1000000];
  5. int pom[1000000];
  6. long long inw = 0;
  7.  
  8. void merge(int p, int k) {
  9.     int s=(p+k) / 2;
  10.     int i=p;
  11.     int j=s+1;
  12.     int x=p;
  13.  
  14.     while (i<=s && j<=k) {
  15.         if (t[i]<=t[j]) {
  16.             pom[x++] = t[i++];
  17.         } else {
  18.             pom[x++] = t[j++];
  19.             inw += (s-i+1);
  20.         }
  21.     }
  22.  
  23.     while (i<=s) {
  24.         pom[x++] = t[i++];
  25.     }
  26.     while (j<=k) {
  27.         pom[x++] = t[j++];
  28.     }
  29.  
  30.     for (int l=p; l<=k; l++)
  31.         t[l] = pom[l];
  32. }
  33.  
  34. void ms(int p, int k) {
  35.     if (p<k) {
  36.         int s = (p+k)/2;
  37.         ms(p, s);
  38.         ms(s+1, k);
  39.         merge(p, k);
  40.     }
  41. }
  42.  
  43. int main() {
  44.     ios_base::sync_with_stdio(0);
  45.     cin.tie(0);
  46.  
  47.     int n;
  48.     cin >> n;
  49.     for (int i=0; i<n; i++) {
  50.         cin >> t[i];
  51.     }
  52.  
  53.     ms(0, n-1);
  54.  
  55.     cout << inw << endl;
  56.     return 0;
  57. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/IPFt0Q
language:
C++14 (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!