Cod sursa(job #2745759)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 26 aprilie 2021 23:18:36
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

struct SegTree {
  int Size;
  vector<int> tree;

  SegTree(int N) {
    Size = 1;
    while (Size < N)
      Size <<= 1;
    tree.resize(Size << 1);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      tree[x] = 1;
      return;
    }
    int mid = (lx + rx) >> 1;
    build(x << 1, lx, mid);
    build(x << 1 | 1, mid + 1, rx);
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
  }

  void update(int x, int lx, int rx, int poz) {
    if (lx == rx) {
      tree[x] = 0;
      return;
    }
    int mid = (lx + rx) >> 1;
    if (poz <= mid)
      update(x << 1, lx, mid, poz);
    else update(x << 1 | 1, mid + 1, rx, poz);
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
  }

  int kth_one(int x, int lx, int rx, int k) {
    if (lx == rx)
      return lx;
    int mid = (lx + rx) >> 1;
    if (k <= tree[x << 1])
      return kth_one(x << 1, lx, mid, k);
    return kth_one(x << 1 | 1, mid + 1, rx, k - tree[x << 1]);
  }
};

const int MAXN = 3e4 + 4;
int p[MAXN], sol[MAXN];

void solve() {
  int N;
  fin >> N;
  for (int i = 1; i <= N; ++i)
    fin >> p[i];
  SegTree tree(N);
  tree.build(1, 1, N);
  for (int i = N; i > 0; --i) {
    int poz = tree.kth_one(1, 1, N, p[i]);
    sol[poz] = i;
    tree.update(1, 1, N, poz);
  }
  for (int i = 1; i <= N; ++i)
    fout << sol[i] << '\n';
}

void close_files() {
  fin.close();
  fout.close();
}

int main() {
  solve();
  close_files();
  return 0;
}