fork(1) download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5.  
  6. void build_tree(ll int *a, ll int s,ll int e, ll int *tree, ll int index)
  7. {
  8. 	if(s==e)
  9. 	{
  10. 		tree[index] = a[s];
  11. 		return;
  12. 	}
  13. 	ll int mid = (s+e)/2;
  14. 	build_tree(a,s,mid,tree,2*index);
  15. 	build_tree(a,mid+1,e,tree,2*index+1);
  16. 	tree[index] += tree[2*index]+tree[2*index+1];
  17. 	return;
  18. }
  19. ll query(ll *tree,ll ss,ll se,ll qs,ll qe ,ll index)
  20. {
  21. 	//complete overlap
  22. 	if(ss>=qs and se<=qe)
  23. 	{
  24. 		return tree[index];
  25. 	}
  26. 	//No Overlap
  27. 	if(qe<ss || qs>se)
  28. 	return 0;
  29.  
  30. 	//partial overlap
  31. 	ll int mid = (ss + se)/2;
  32. 	ll int left = query(tree,ss,mid,qs,qe,2*index);
  33. 	ll int right = query(tree,mid+1,se,qs,qe,2*index+1);
  34. 	return left+right;
  35. }
  36. //point update
  37. void point_update(ll  *tree, ll ss,ll se, ll i,ll inc,ll index)
  38. {
  39. 	if(i>se || i<ss)
  40. 	return;
  41. 	if(ss == se)
  42. 	{
  43. 		tree[index] = inc;
  44. 		return;
  45. 	}
  46. 	ll int mid = (ss + se)/2;
  47. 	point_update(tree,ss,mid,i,inc,2*index);
  48. 	point_update(tree,mid+1,se,i,inc,2*index+1);
  49. 	tree[index] = tree[2*index]+tree[2*index+1];
  50. 	return;
  51. }
  52.  
  53. void solve()
  54. {
  55. 	int n;
  56. 	cin>>n;
  57.  
  58. 	ll a[2*n+1];
  59. 	for(int i=0;i<2*n;i++)
  60. 	cin>>a[i];
  61. 	ll tree[4*2*n+1]={0};
  62.  
  63.  
  64. 	// for(int i=1;i<=4*n;i++)
  65. 	// cout<<tree[i]<<endl;
  66. 	vector<ll>ans(n+1);
  67.  
  68. 	unordered_map<ll,ll>ump;
  69. 	for(int k=1;k<=2;k++)
  70. 	{
  71. 		for(int i=0;i<2*n;i++)
  72. 		{
  73. 			if(ump.find(a[i])!=ump.end())
  74. 			{
  75. 				int pos = ump[a[i]];
  76. 				ump.erase(a[i]);
  77.  
  78. 				int nst_sg = query(tree,0,2*n-1,pos,i,1);
  79. 				ans[a[i]]  += (nst_sg - 1);
  80. 				// update with one
  81. 				point_update(tree,0,2*n-1,pos,0,1);
  82. 			}
  83. 			else
  84. 			{
  85. 				ump[a[i]] = i;
  86. 				point_update(tree,0,2*n-1,i,1,1);
  87. 			}
  88. 		}
  89. 		ump.clear();
  90. 		memset(tree,0,sizeof(tree));
  91. 		reverse(a,a+2*n);
  92. 	}
  93.  
  94. 	for(int i=1;i<=n;i++)
  95. 	cout<<ans[i]<<" ";
  96. 	cout<<endl;
  97.  
  98. }
  99.  
  100.  
  101. int main()
  102. {
  103. 	ios_base::sync_with_stdio(false); 
  104.     	cin.tie(NULL); 
  105.  
  106.     ll int t=1;
  107. 	 // cin>>t;
  108. 	while(t--)
  109. 	{  
  110.       solve();
  111.     }
  112.  
  113. 	return 0;
  114. }
  115.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:61:10: error: variable-sized object may not be initialized
        ll tree[4*2*n+1]={0};
                ^~~~~~~
1 error generated.
stdout
copy 
Standard output is empty
https://ideone.com/TTbbUD
language:
C++14 (clang 8.0)
created:
4 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!