fork(1) download
copy 
  1. #include<cstdio>
  2. #define M 1000
  3. typedef long long ll;
  4. ll arr[M],temp[M];
  5. ll count;
  6.  
  7. void merge(ll x,ll y,ll mid)
  8. {
  9.     ll i,j,k=0;
  10.     i=x;
  11.     j=mid+1;
  12.     ll n1;
  13.     while(i<=mid&&j<=y)
  14.     {
  15.  
  16.         if(arr[i]>arr[j])
  17.         {
  18.             n1=mid-i+1;
  19.         //    printf("in %lld %lld %lld %lld\n",n1,mid,arr[i],arr[j]);
  20.             count+=n1;
  21.             temp[k++]=arr[j++];
  22.         }
  23.         else{
  24.             temp[k++]=arr[i++];
  25.         //    printf("else %lld\n",i);
  26.  
  27.         }
  28.     }
  29.  
  30.         while(i<=mid)
  31.            temp[k++]=arr[i++];
  32.  
  33.         while(j<=y)
  34.             temp[k++]=arr[j++];
  35.  
  36.  
  37.     for(ll p=0,i=x;p<k;p++,i++)
  38.     {
  39.         arr[i]=temp[p];
  40.  
  41.     }
  42. }
  43.  
  44. void part(ll x,ll y)
  45. {
  46.     if(x<y)
  47.     {
  48.         ll mid=(x+y)/2;
  49.         part(x,mid);
  50.         part(mid+1,y);
  51.         merge(x,y,mid);
  52.     }
  53. }
  54. int main()
  55. {
  56.     ll t;
  57.     scanf("%lld",&t);
  58.     while(t--)
  59.     {
  60.         char c=getchar();
  61.         ll n;
  62.         count=0;
  63.         scanf("%lld",&n);
  64.         for(ll i=0;i<n;i++)
  65.             scanf("%lld",&arr[i]);
  66.  
  67.         part(0,n-1);
  68.  
  69.         printf("%lld\n",count);
  70.     }
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 3116KB
comments (?)
stdin
copy 
1

5
2
3
8
6
1
stdout
copy 
5
https://ideone.com/bTTfTE
language:
C++ (gcc 8.3)
created:
10 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!