Pagini recente » Istoria paginii runda/oji20091112/clasament | Cod sursa (job #1594490) | Cod sursa (job #1126491) | Cod sursa (job #1245280) | Cod sursa (job #2681639)
#include <iostream>
#include <fstream>
#include <cassert>
const int NMAX = 3e4;
int n;
int seg_tree[3 * NMAX];
int a[1 + NMAX];
int order[1 + NMAX];
void update(int node, int left, int right, int ind, int val) {
if (left == right) {
assert(left == ind);
seg_tree[node] = val;
return;
}
int mid = (left + right) / 2;
int left_child = 2 * node;
int right_child = 2 * node + 1;
if (ind <= mid)
update(left_child, left, mid, ind, val);
else
update(right_child, mid + 1, right, ind, val);
seg_tree[node] = seg_tree[left_child] + seg_tree[right_child];
}
int query(int node, int left, int right, int q_left, int q_right) {
if (left > q_right || right < q_left)
return 0;
if (q_left <= left && right <= q_right)
return seg_tree[node];
int mid = (left + right) / 2;
int left_child = 2 * node;
int right_child = 2 * node + 1;
return query(left_child, left, mid, q_left, q_right) + query(right_child, mid + 1, right, q_left, q_right);
}
void read() {
std::ifstream in("schi.in");
in >> n;
for (int i = 1; i <= n; ++i)
in >> a[i];
in.close();
}
int main() {
read();
for (int i = n; i >= 1; --i) {
int prev_sum = query(1, 1, n, 1, a[i]);
int new_pos = a[i] + prev_sum;
int new_sum = query(1, 1, n, 1, new_pos);
while (new_sum != prev_sum) {
new_pos = a[i] + new_sum;
prev_sum = new_sum;
new_sum = query(1, 1, n, 1, new_pos);
}
update(1, 1, n, new_pos, 1);
order[new_pos] = i;
}
std::ofstream out("schi.out");
for (int i = 1; i <= n; ++i)
out << order[i] << '\n';
out.close();
return 0;
}