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 = 0; i < treeSize; i++) {
  37.             if (i < n)
  38.                 used[treeSize - 1 + i] = 1;
  39.             else
  40.                 used[treeSize - 1 + i] = 0;
  41.         }
  42.  
  43.         for (ll i = treeSize - 2; i >= 0; i--)
  44.             used[i] = used[2*i+1] + used[2*i+2];
  45.     }
  46.  
  47.     void change(ll k, ll i, ll l, ll r) {
  48.         if (r-l == 1) {
  49.             used[i]  = 0;
  50.             return;
  51.         }
  52.  
  53.         ll mid = l+(r-l)/2;
  54.         if (k < mid) change(k, 2*i+1, l, mid);
  55.         else change(k, 2*i+2, mid, r);
  56.  
  57.         used[i] = used[2*i+1] + used[2*i+2];
  58.     }
  59.  
  60.     void change(ll k) {
  61.         change(k, 0, 0, treeSize);
  62.     }
  63.  
  64.     ll query(ll k, ll i, ll l, ll r) {
  65.         if (r-l == 1) {
  66.             return l;
  67.         }
  68.  
  69.         ll mid = l+(r-l)/2;
  70.         if (used[2*i+2] >= k)
  71.             return query(k, 2*i+2, mid, r);
  72.         return query(k - used[2*i+2], 2*i+1, l, mid);
  73.     }
  74.  
  75.     ll query(ll k) {
  76.        ll x =  query(k, 0, 0, treeSize);
  77.         change(x);
  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.     vector<ll> ans(n, 0);
  89.     for (ll i = n-1; i >= 0; i--) {
  90.         ll idx = st.query(v[i]+1);
  91.         ans[i] = idx+1;
  92.     }
  93.  
  94.     for (auto x : ans) cout << x << " ";
  95.     cout << "\n";
  96. }
  97.  
  98. int main() {
  99.     FAST;
  100. #ifndef ONLINE_JUDGE
  101.     freopen("input.txt", "r", stdin);
  102.     freopen("output.txt", "w", stdout);
  103. #endif
  104.     int tt = 1; //cin >> tt;
  105.     while (tt--) {
  106.         solve();
  107.         //cout << "Case #" << c++ << ": ";
  108.     }
  109.     return 0;
  110. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
https://ideone.com/ZBdWhb
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!