Pagini recente » Cod sursa (job #487735) | Cod sursa (job #2355603) | Cod sursa (job #2580632) | Cod sursa (job #1387442) | Cod sursa (job #3151480)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
struct BinaryIndexedTree{
// [1-indexed]
// [uses <vector>, <algorithm>]
int n;
vector <int> tree;
BinaryIndexedTree(int Size) : n(Size) { // Constructor
tree.resize(n + 1, 0);
}
void Update(int i, int val){ // Adds a value to a specified place whitin the BIT
while(i <= n){
tree[i] += val;
i += (i & -i);
}
}
int Query(int i){ // Returns the sum up to specified place
int sum = 0;
while(i > 0){
sum += tree[i];
i -= (i & -i);
}
return sum;
}
int RangeQuery(int i, int j){ // Retruns the sum between two places
return Query(j) - Query(i - 1);
}
int Src(int val){ // Returns the first place where the sum is equal to val
int sum = 0, pos = 1 << 30, right = 0;
while(pos != 0){
if(right + pos <= n && sum + tree[right + pos] < val){
sum += tree[right + pos];
right += pos;
}
pos >>= 1;
}
return right + 1;
}
};
int main()
{
int n;
vector <int> rank, s;
fin >> n;
rank.resize(n + 1);
s.resize(n + 1);
BinaryIndexedTree BIT(n);
for(int i = 1; i <= n; i ++) {
fin >> rank[i];
BIT.Update(i, 1);
}
for(int i = n; i >= 1; i --) {
int pos = rank[i];
pos = BIT.Src(pos);
BIT.Update(pos, -1);
s[pos] = i;
}
for(int i = 1; i <= n; i++)
fout << s[i] << "\n";
return 0;
}