fork(2) 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 i=0;i<2*n;i++)
  70. 	{
  71. 		if(ump.find(a[i])!=ump.end())
  72. 		{
  73. 			int pos = ump[a[i]];
  74. 			ump.erase(a[i]);
  75. 			int nst_sg = query(tree,0,2*n-1,pos,i,1);
  76. 			ans[a[i]]  = nst_sg;
  77. 			// update with one
  78. 			point_update(tree,0,2*n-1,pos,1,1);
  79. 		}
  80. 		else
  81. 		{
  82. 			ump[a[i]] = i;
  83.  
  84. 		}
  85. 	}
  86. 	for(int i=1;i<=n;i++)
  87. 	cout<<ans[i]<<" ";
  88. 	cout<<endl;
  89.  
  90. }
  91.  
  92.  
  93. int main()
  94. {
  95. 	ios_base::sync_with_stdio(false); 
  96.     	cin.tie(NULL); 
  97.  
  98.     ll int t=1;
  99. 	 // cin>>t;
  100. 	while(t--)
  101. 	{  
  102.       solve();
  103.     }
  104.  
  105. 	return 0;
  106. }
  107.  
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/uPITmL
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!