fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5.  
  6. ll inv[100005]={0};
  7.  
  8. ll query(ll *tree,ll ss,ll se,ll qs,ll qe ,ll index)
  9. {
  10. 	//complete overlap
  11. 	if(ss>=qs and se<=qe)
  12. 	{
  13. 		return tree[index];
  14. 	}
  15. 	//No Overlap
  16. 	if(qe<ss || qs>se)
  17. 	return 0;
  18.  
  19. 	//partial overlap
  20. 	ll int mid = (ss + se)/2;
  21. 	ll int left = query(tree,ss,mid,qs,qe,2*index);
  22. 	ll int right = query(tree,mid+1,se,qs,qe,2*index+1);
  23. 	return left+right;
  24. }
  25. //point update
  26. void point_update(ll  *tree, ll ss,ll se, ll i,ll inc,ll index)
  27. {
  28. 	if(i>se || i<ss)
  29. 	return;
  30. 	if(ss == se)
  31. 	{
  32. 		tree[index] += inc;
  33. 		return;
  34. 	}
  35. 	ll int mid = (ss + se)/2;
  36. 	point_update(tree,ss,mid,i,inc,2*index);
  37. 	point_update(tree,mid+1,se,i,inc,2*index+1);
  38. 	tree[index] = tree[2*index]+tree[2*index+1];
  39. 	return;
  40. }
  41. // 
  42. void solve()
  43. {
  44. 	int n;
  45. 	cin>>n;
  46.  
  47. 	ll a[n+1]={0};
  48. 	for(int i=1;i<=n;i++)
  49. 	cin>>a[i];
  50. 	ll tree[4*n+1]={0};
  51. 	for(int i=1;i<=n;i++)
  52. 	{
  53. 		int x = query(tree,1,n,a[i]+1,n,1);
  54. 		inv[a[i]]+=x;
  55. 		point_update(tree,1,n,a[i],1,1);
  56. 	}
  57. 	for(int i=1;i<=n;i++)
  58. 	cout<<inv[a[i]]<<" ";
  59.  
  60. 	return;
  61.  
  62. }
  63. int main()
  64. {
  65. 	ios_base::sync_with_stdio(false); 
  66.     	cin.tie(NULL); 
  67.  
  68.  
  69.     ll int t=1;
  70. 	 // cin>>t;
  71. 	while(t--)
  72. 	{  
  73.       solve();
  74.     }
  75.  
  76. return 0;
  77. }
  78.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:47:7: error: variable-sized object may not be initialized
        ll a[n+1]={0};
             ^~~
prog.cpp:50:10: error: variable-sized object may not be initialized
        ll tree[4*n+1]={0};
                ^~~~~
2 errors generated.
stdout
copy 
Standard output is empty
https://ideone.com/8v15jw
language:
C++14 (clang 8.0)
created:
3 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!