Pagini recente » Cod sursa (job #1452740) | Cod sursa (job #2140302) | Istoria paginii utilizator/banutraul1234567 | Cod sursa (job #1958249) | Cod sursa (job #1507930)
#include <fstream>
#include <vector>
#include <cstdlib>
using namespace std;
ifstream fin ("schi.in");
ofstream fout ("schi.out");
class Node
{
public :
short val;
Node *left;
Node *right;
Node()
{
val = 0;
left = NULL;
right = NULL;
}
};
short n, Sol[30010];
Node *Root;
void Update_Tree(Node *node, short left, short right, const short poz, const short value)
{
if (left == right)
{
node -> val += value;
return;
}
short mid = (left + right) >> 1;
if (poz <= mid)
{
if (node -> left == NULL) node -> left = new Node;
Update_Tree(node -> left, left, mid, poz, value);
}
else
{
if (node -> right == NULL) node -> right = new Node;
Update_Tree(node -> right, mid + 1, right, poz, value);
}
/// Actualizez
if (node -> left != NULL)
{
node -> val = node -> left -> val;
if (node -> right != NULL)
{
node -> val += node -> right -> val;
}
}
else if (node -> right != NULL)
{
node -> val += node -> right -> val;
}
}
void Query_Tree(Node *node, short left, short right, const short stanga, const short dreapta, short &sum)
{
if (stanga <= left && right <= dreapta)
{
sum += node -> val;
return;
}
short mid = (left + right) >> 1;
if (stanga <= mid) Query_Tree(node -> left, left, mid, stanga, dreapta, sum);
if (dreapta > mid) Query_Tree(node -> right, mid + 1, right, stanga, dreapta, sum);
}
short Binary_Search(short value)
{
short i = n, step = 1;
while(step <= n) step <<= 1;
step >>= 1;
while (step)
{
if (i - step >= 1)
{
short sum = 0;
Query_Tree(Root, 1, n, 1, i - step, sum);
if (sum >= value)
{
i -= step;
}
}
step >>= 1;
}
return i;
}
Node *Build_Tree(vector < short > &Data)
{
Node *Root = new Node;
for (short i = 0; i < Data.size(); i++)
{
Update_Tree(Root, 1, Data.size(), i + 1, 1);
}
return Root;
}
int main()
{
fin >> n;
vector < short > Data(n);
for (short i = 0; i < n; i++)
{
fin >> Data[i];
}
Root = Build_Tree(Data);
for (short i = Data.size() - 1; i >= 0; i--)
{
short poz = Binary_Search(Data[i]);
Sol[poz] = i + 1;
Update_Tree(Root, 1, Data.size(), poz, -1);
}
for (short i = 1; i <= n; i++)
{
fout << Sol[i] << '\n';
}
fout.close();
return 0;
}