Mai intai trebuie sa te autentifici.
Cod sursa(job #2017414)
Utilizator | Data | 1 septembrie 2017 09:39:00 | |
---|---|---|---|
Problema | Schi | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.03 kb |
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("schi.in");
ofstream cout("schi.out");
const int MAX = 3e4 + 1;
class Segmenet_Tree {
public:
Segmenet_Tree(int n) {
this -> n = n;
// this -> arb.resize((MAX << 2));
}
void update(int target, int val) {
_update(target, val, 1, this -> n, 1);
}
int query(int target_st, int target_dr) {
return _query(target_st, target_dr, 1, this -> n, 1);
}
private:
int n;
int arb[MAX << 2];
void _update(int target, int val, int st, int dr, int nod) {
if (st == dr) {
arb[nod] = val;
return;
}
int middle = (st + dr) >> 1;
if (target <= middle) {
_update(target, val, st, middle, nod << 1);
}
else {
_update(target, val, middle + 1, dr, nod << 1 | 1);
}
arb[nod] = arb[nod << 1] + arb[nod << 1 | 1];
}
int _query(int target_st, int target_dr, int st, int dr, int nod) {
if (target_st <= st and dr <= target_dr) {
return arb[nod];
}
int middle = (st + dr) >> 1;
int left = 0;
int right = 0;
if (target_st <= middle) {
left = _query(target_st, target_dr, st, middle, nod << 1);
}
if (target_dr > middle) {
right = _query(target_st, target_dr, middle + 1, dr, nod << 1 | 1);
}
return left + right;
}
};
int main(int argc, char const *argv[]) {
int n;
cin >> n;
Segmenet_Tree *T = new Segmenet_Tree(n);
vector < int > v (MAX);
for (int i = 1; i <= n; i ++) {
cin >> v[i];
}
for (int i = 1; i <= n; i ++) {
T -> update(i, 1);
}
vector < int > sol (MAX);
for (int i = n; i >= 1; i --) {
int ans = n + 1;
int seek_val = v[i];
for (int bit = log2(n) + 1; bit >= 0; bit --) {
if (ans - (1 << bit) < 1) continue;
int found_val = T -> query(1, (ans - (1 << bit)));
if (found_val < seek_val) continue;
ans -= (1 << bit);
}
T -> update(ans, 0);
sol[ans] = i;
}
for (int i = 1; i <= n; i ++) {
cout << sol[i] << '\n';
}
delete T;
return 0;
}