fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4. long long sum=0;
  5. void print(int *a,int s)
  6. {
  7. for(int i=0;i<s;i++)
  8. {cout<<a[i]<<" ";}
  9. cout<<"\n";
  10.  
  11. }
  12.  
  13. long si=0;
  14. int* merge(int ar[],int s)
  15. {
  16. int l1=s/2,l2=s-s/2;
  17. int ar1[l1],ar2[l2];
  18. int *a1,*a2;
  19. if(s>1)
  20. {
  21. for(int i=0;i<l1;i++)
  22. ar1[i]=ar[i];
  23.  
  24. int k=0;
  25. int l22=(s%2==0)?l2:l2-1;
  26. for(int i=l22;i<s;i++)
  27. ar2[k++]=ar[i];
  28.  
  29.  
  30. a1=merge(ar1,l1);
  31. a2=merge(ar2,l2);
  32.  
  33. int c1=0,c2=0;
  34. for(int i=0;i<s;i++)
  35. {
  36. if(c1==l1)
  37. {while(c2<l2)
  38. {ar[i++]=a2[c2++]; } break;}
  39.  
  40. if(c2==l2)
  41. {while(c1<l1)
  42. {ar[i++]=a1[c1++]; } break;}
  43.  
  44. if(a1[c1]<a2[c2])
  45. {ar[i]=a1[c1++];   sum=sum+(l2-c2)*a1[c1-1];}
  46. else 
  47. {ar[i]=a2[c2++];  si=si+(l1-c1);}
  48. }
  49.  
  50. //print(ar,sizeof(ar)/sizeof(int));
  51. }//if s>1
  52. return ar;
  53. }
  54.  
  55.  
  56. int main()
  57. {
  58.  
  59. int t,n;
  60. scanf("%d",&t);
  61. for(int i=0;i<t;i++)
  62. {
  63. sum=0;
  64. scanf("%d",&n);
  65. int ar[n];
  66. for(int i=0;i<n;i++)
  67. scanf("%d",&ar[i]);
  68.  
  69.  
  70. int *ar1=merge(ar,n);
  71. printf("%lld\n",sum);
  72. }
  73.  
  74.  
  75. }
Success #stdin #stdout 0.02s 2728KB
comments (?)
stdin
copy 
2 
3 
1 1 1 
5 
1 2 3 1 2
stdout
copy 
0
6
https://ideone.com/bnz52
language:
C++ (gcc 8.3)
created:
13 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!