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