fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ld long double
  4. #define ll long long
  5. #define pb push_back
  6. #define fin(a, n) for(int i = a; i < n; i++)
  7. #define fjn(a, n) for(int j = a; j < n; j++)
  8. #define all(a) a.begin(),a.end()
  9. #define allr(a) a.rbegin(),a.rend()
  10. #define FAST ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
  11.  
  12. using namespace std;
  13.  
  14. const double pi = acos(-1);
  15. const int N = 1000+20;
  16. const ll oo = 0x3f3f3f3f3f3f3f3f;
  17. const int MOD = 1e9+7;
  18.  
  19. string di[] = {"D","L", "U", "R", "UL", "UR", "DL", "DR"};
  20. int dx[] = {+1, +0, +0, -1, -1, -1, +1, +1};
  21. int dy[] = {+0, -1, +1, +0, -1, +1, -1, +1};
  22. char dc[] = {'D', 'L', 'R', 'U'};
  23.  
  24. struct segTree {
  25.     ll treeSize;
  26.     vector<ll> used;
  27.     ll n;
  28.     segTree(ll n) {
  29.         treeSize = 1;
  30.         this->n = n;
  31.         while (treeSize < n) treeSize <<= 1;
  32.         used.resize(2 * treeSize, -oo);
  33.     }
  34.  
  35.     void build() {
  36.         for (ll i = treeSize-1; i >= 0; i--) {
  37.             used[i] = 1;
  38.             if (i <= treeSize/2) {
  39.                 used[i] = used[2*i+1] + used[2*i+2];
  40.             }
  41.         }
  42.     }
  43.  
  44.     void change(ll k, ll i, ll l, ll r) {
  45.         if (r-l == 1) {
  46.             used[i]  = 0;
  47.             return;
  48.         }
  49.  
  50.         ll mid = l+(r-l)/2;
  51.         if (used[2*i+2] >= k) {
  52.              change(k, 2*i+2, mid, r);
  53.         }
  54.         else change(used[2*i+1]-k, 2*i+1, l, mid);
  55.  
  56.         used[i] = used[2*i+1] + used[2*i+2];
  57.     }
  58.  
  59.     void change(ll k) {
  60.         change(k, 0, 0, treeSize);
  61.     }
  62.  
  63.     ll query(ll k, ll i, ll l, ll r) {
  64.         if (r-l == 1) {
  65.             return i;
  66.         }
  67.  
  68.         ll mid = l+(r-l)/2;
  69.         if (used[2*i+2] >= k) {
  70.             return query(k, 2*i+2, mid, r);
  71.         }
  72.         return query(used[2*i+1]-k, 2*i+1, l, mid);
  73.     }
  74.  
  75.     ll query(ll k) {
  76.        ll x =  query(k, 0, 0, treeSize);
  77.         change(k);
  78.         return x;
  79.     }
  80. };
  81.  
  82. void solve() {
  83.     ll n;  cin >> n;
  84.     vector<ll> v(n);
  85.     fin(0, n) cin >> v[i];
  86.     segTree st(n);
  87.     st.build();
  88.  
  89.     for (int i = n-1; i >= 0; i--) {
  90.         ll idx = st.query(v[i]);
  91.         cout << idx << " ";
  92.     }
  93.     cout << "\n";
  94. }
  95.  
  96. int main() {
  97.     FAST;
  98. #ifndef ONLINE_JUDGE
  99.     freopen("input.txt", "r", stdin);
  100.     freopen("output.txt", "w", stdout);
  101. #endif
  102.     int tt = 1; //cin >> tt;
  103.     while (tt--) {
  104.         solve();
  105.         //cout << "Case #" << c++ << ": ";
  106.     }
  107.     return 0;
  108. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/UziYKz
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
2 days 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!