Pagini recente » Cod sursa (job #433029) | Cod sursa (job #1990942) | Romanii medaliati la IOI | Cod sursa (job #2187567) | Cod sursa (job #2547639)
#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>
#define INF 0x3f3f3f3f
using namespace std;
#ifdef DEBUG
string name = "data";
#else
string name = "schi";
#endif
ifstream fin(name + ".in");
ofstream fout(name + ".out");
struct Event {
int p;
int v;
};
vector<Event> q;
#define MAXN 30005
int aib[MAXN];
int n;
int result[MAXN];
int nrz(int x) {
return x & (~x + 1);
}
void update(int x, int v) {
while (x <= n ) {
aib[x] += v;
x += nrz(x);
}
}
int query(int x) {
int result = 0;
while (x > 0) {
result += aib[x];
x -= nrz(x);
}
return result;
}
int binSearch(int low, int high, int target) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
int q = query(mid);
if (q == target && (mid == low || query(mid - 1) != target)) {
return mid;
}
if (q >= target) {
return binSearch(low, mid - 1, target);
}
return binSearch(mid + 1, high, target);
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i) {
int x;
fin >> x;
q.push_back({x, i});
}
reverse(q.begin(), q.end());
for (int i = 1; i <= n; ++i) {
update(i, 1);
}
for (auto x: q) {
int ndx = binSearch(1, n, x.p);
update(ndx, -1);
result[ndx] = x.v;
}
for (int i = 1; i <= n; ++i) {
fout << result[i] << "\n";
}
return 0;
}