fork(10) 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. int count ;
  21. void merge(int low, int high, int mid)
  22. {
  23.     int i, j, k;
  24.     i = low;
  25.     k = low;
  26.     j = mid + 1;
  27.     while (i <= mid && j <= high)
  28.     {
  29.         if (a[i] < a[j])
  30.         {
  31.             c[k] = a[i];
  32.             k++;
  33.             i++;
  34.         }
  35.         else
  36.         {
  37.             c[k] = a[j];
  38.             k++;
  39.             j++;
  40.          //   cout<<a[i]<<" "<<mid<<" "<<i<<"\n";
  41.             count += mid - i+1; 
  42.         }
  43.     }
  44.     while (i <= mid)
  45.     {
  46.         c[k] = a[i];
  47.         k++;
  48.         i++;
  49.     }
  50.     while (j <= high)
  51.     {
  52.         c[k] = a[j];
  53.         k++;
  54.         j++;
  55.     }
  56.     for (i = low; i < k; i++)
  57.     {
  58.         a[i] = c[i];
  59.     }
  60. }
  61. int main()
  62. {
  63.     //int a[20], i, b[20];
  64.     int T;
  65.     cin>>T;
  66.     while(T--){
  67. 	    //cout<<"enter  the elements\n";
  68. 	    int N;
  69. 	    cin>>N;
  70. 	    count =0;
  71. 	    a.clear(); a.resize(N);
  72. 	    c.clear(); c.resize(N);
  73. 	    for (int i = 0; i < N; i++)
  74. 	    {
  75. 	        cin>>a[i];
  76. 	    }
  77. 	    mergesort(0, N-1);
  78.  
  79.     	cout<<count<<"\n";
  80. 	}
  81. }
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
3

3
3
1
2

5
2
3
8
6
1

10
1000000
100000
1000
100000
1
9999
100000
98
99909
100000
stdout
copy 
2
5
29
https://ideone.com/nmvl7i
language:
C++14 (gcc 8.3)
created:
8 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!