Pagini recente » Cod sursa (job #1000362) | Cod sursa (job #1822276) | Cod sursa (job #2935250) | Cod sursa (job #2941162) | Cod sursa (job #2944221)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
int const NMAX = 30000;
int arr[1 + NMAX];
int ski[1 + NMAX];
struct SegmentTree {
vector <int> seg;
SegmentTree(int n = 0) {
seg.resize(4 * n);
}
void update(int node, int from, int to, int pos, int x) {
if(from == to){
seg[node] = 1;
}else {
int mid = (from + to) / 2;
if(pos <= mid) {
update(node * 2, from, mid, pos, x);
}else {
update(node * 2 + 1, mid+1, to, pos, x);
}
seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
}
int query(int node, int from, int to, int x, int y) {
if(from == x && to == y) {
return seg[node];
}else {
int mid = (from + to) / 2, ans = 0;
if(x <= mid) {
ans += query(node * 2, from, mid, x, min(mid, y));
}
if(mid < y) {
ans += query(node * 2 + 1, mid+1, to, max(x, mid+1), y);
}
return ans;
}
}
};
int main() {
int n;
in >> n;
for(int i = 1;i <= n;i++) {
in >> arr[i];
}
SegmentTree seg(n);
for(int i = n;i >= 1;i--) {
int add = seg.query(1, 1, n, 1, arr[i]), removed;
removed = add;
//cout << "/\n";
while(add != 0) {
arr[i] = arr[i] + add;
add = seg.query(1, 1, n, 1, arr[i]) - removed;
removed += add;
}
//cerr << arr[i] << ' ' << add << ' ' << add + arr[i] << '\n';
ski[arr[i]] = i;
seg.update(1, 1, n, arr[i], 1);
}
//cerr << '\n';
for(int i = 1;i <= n;i++) {
out << ski[i] << '\n';
}
return 0;
}