Pagini recente » Cod sursa (job #2550296) | Cod sursa (job #390748) | Cod sursa (job #1853329) | Cod sursa (job #3180545) | Cod sursa (job #2756599)
#include <iostream>
#include <fstream>
#define NMAX 30000
using namespace std;
ifstream fin ("schi.in");
ofstream fout ("schi.out");
int A, B;
int pozSterg;
int tree[4 * NMAX + 1];
int v[NMAX + 1];
int rez[NMAX + 1];
void creareArbore(int node, int left, int right){
tree[node] = right - left + 1;
if(left == right){
return;
}
int mid = left + (right - left) / 2;
creareArbore(node * 2, left, mid);
creareArbore(node * 2 + 1, mid + 1, right);
}
int query(int node, int left, int right){
if(left == right){
return tree[node];
}
int mid = left + (right - left) / 2;
int rez1 = 0, rez2 = 0;
if(A <= mid){
rez1 = query(node * 2, left, mid);
}
if(B >= mid + 1){
rez2 = query(node * 2 + 1, mid + 1, right);
}
return rez1 + rez2;
}
void sterg(int node, int left, int right){
if(left == right){
tree[node] = 0;
return;
}
int mid = left + (right - left) / 2;
if(pozSterg <= mid){
sterg(node * 2, left, mid);
}
else {
sterg(node * 2 + 1, mid + 1, right);
}
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int main()
{
int N;
fin >> N;
for(int i = 1; i <= N; i++){
fin >> v[i];
}
creareArbore(1, 1, N);
for(int i = N; i >= 1; i--){
int lo = 0;
int hi = N + 1;
while(hi - lo > 1){
int mid = lo + (hi - lo) / 2;
A = 1;
B = mid; //[A, B] imi da intervalul pe care vreau suma
if(query(1, 1, N) >= v[i]){
hi = mid;
}
else{
lo = mid;
}
}
//raspunsul se afla in hi
rez[ hi ] = i;
pozSterg = hi;
sterg(1, 1, N); //sterg hi
}
for(int i = 1; i <= N; i++){
fout << rez[i] << "\n";
}
return 0;
}