Pagini recente » Cod sursa (job #2677530) | Cod sursa (job #618554) | Cod sursa (job #2023103) | Cod sursa (job #352389) | Cod sursa (job #1147614)
#include <fstream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
using namespace std;
class IntervalTree {
vector<unsigned short> sum;
int n;
int leftSon(const int& node) {
return node << 1;
}
int rightSon(const int& node) {
return (node << 1) + 1;
}
void buildTree(int node, int l,int r) {
if (l == r) {
sum[node] = 1;
return;
}
int mid = (l + r) >> 1;
buildTree(leftSon(node), l, mid);
buildTree(rightSon(node), mid + 1, r);
sum[node] = sum[leftSon(node)] + sum[rightSon(node)];
}
public:
IntervalTree(int n_ = 1) {
n = n_;
sum.resize(n << 2);
buildTree(1, 1, n);
}
void update(int node, int l, int r, int pos) {
if (l == r) {
sum[node] = 0;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
update(leftSon(node), l, mid, pos);
} else {
update(rightSon(node), mid + 1, r, pos);
}
sum[node] = sum[leftSon(node)] + sum[rightSon(node)];
}
int query(int node, int l, int r,int x) {
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
if (sum[leftSon(node)] < x) {
return query(rightSon(node), mid + 1, r, x - sum[leftSon(node)]);
}
return query(leftSon(node), l, mid, x);
}
};
int main()
{
ifstream cin("schi.in");
ofstream cout("schi.out");
int n;
cin >> n;
vector<int> p(n);
vector<int> ret(n);
IntervalTree tree(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
ret[i] = i;
}
for (int i = n - 1; i >= 0; i--) {
p[i] = tree.query(1, 1, n, p[i]);
tree.update(1, 1, n, p[i]);
}
sort(ret.begin(), ret.end(), [&](const int& i, const int& j) {
return p[i] < p[j];
});
for (int i = 0; i < n; i++) {
cout << ret[i] + 1 << "\n";
}
return 0;
}