fork(4) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<int> a;
  6. vector<int> c;
  7. void merge(int low, int high, int mid);
  8. void mergesort(int low, int high)
  9. {
  10.  int mid;
  11.  if (low < high)
  12.  {
  13.      mid=(low+high)/2;
  14.      mergesort(low,mid);
  15.      mergesort(mid+1,high);
  16.      merge(low,high,mid);
  17.  }
  18. return ;
  19. }
  20.  
  21. long long count ; //to store the inversion count
  22. void merge(int low, int high, int mid)
  23. {
  24. int i, j, k;
  25. i = low;
  26. k = low;
  27. j = mid + 1;
  28. // standard merging from merge sort
  29. while (i <= mid && j <= high)
  30. {
  31.     if (a[i] < a[j])
  32.     {
  33.         c[k] = a[i];
  34.         k++;
  35.         i++;
  36.     }
  37.     else
  38.     {
  39.         c[k] = a[j];
  40.         k++;
  41.          j++;
  42.       //   cout<<a[i]<<" "<<mid<<" "<<i<<"\n";
  43.          count += (long long)mid - (long long) i + 1L; // This is where the trick occurs, if X > Y,
  44.          //eg. in [3, 4, 5] and [1,2]
  45.          //if(3>1) then 4,5 is obviously greater then 1, thus making count as mid - i+1              
  46.      }
  47.  }
  48. while (i <= mid)
  49. {
  50.     c[k] = a[i];
  51.     k++;
  52.     i++;
  53. }
  54. while (j <= high)
  55. {
  56.     c[k] = a[j];
  57.     k++;
  58.     j++;
  59. }
  60. for (i = low; i < k; i++)
  61. {
  62.     a[i] = c[i];
  63.  }
  64. }
  65. int main()
  66. {
  67. //int a[20], i, b[20];
  68. int T;
  69. cin>>T;
  70. while(T--){
  71.     //cout<<"enter  the elements\n";
  72.     int N;
  73.     cin>>N;
  74.     count =0;
  75.     a.clear(); a.resize(N);
  76.     c.clear(); c.resize(N);
  77.     for (int i = 0; i < N; i++)
  78.     {
  79.         cin>>a[i];
  80.     }
  81.     mergesort(0, N-1);
  82.  
  83.     cout<<count<<"\n";
  84. }
  85. }
Runtime error #stdin #stdout #stderr 0.54s 529408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/16kEoV
problem INVCNT, based on SPOJ submission 14396343 (C++14), 2015-06-05 10:03:37
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!