Cod sursa(job #2774975)

Utilizator AACthAirinei Andrei Cristian AACth Data 13 septembrie 2021 18:52:05
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.18 kb
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
#define cin f
#define cout g
const int Max = 3e4 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
namespace SegmentTree{
    struct Node{
        int val;
    }tree[4*Max];
    int rev[Max];
    Node merge(Node n1, Node n2)
    {
        Node ans;
        ans.val = n1.val+n2.val;
        return ans;
    }
    //remember to call init and update n
    int n;
    void init(int where , int left, int right)
    {
        if(left == right)
        {
            tree[where].val = 1;
            rev[left] = where;
            return;
        }
        int mid = (left + right) / 2;
        init(2*where,left,mid);
        init(2*where + 1,mid+1,right);
        tree[where] = merge(tree[2*where],tree[2*where+1]);
    }
    void propagate(int where)
    {
        if(where)
        {
            tree[where] = merge(tree[2*where],tree[2*where+1]);
            propagate(where / 2);
        }
    }
    void Update(int pos,int val)
    {
        int pos_in_tree = rev[pos];
        tree[pos_in_tree].val = val;
        propagate(pos_in_tree / 2);
    }
    int left_limit,right_limit;
    vector<Node> elem;
    void QueryRange(int where, int left, int right)
    {
        if(left_limit <= left and right <= right_limit)
        {
            //sunt pe o pozitie pe care pot considera nodul
            elem.push_back(tree[where]);
            return;
        }
        int mid = (left + right) / 2;
        if(left_limit <= mid)
            QueryRange(2*where,left,mid);
        if(mid + 1 <= right_limit)
            QueryRange(2*where + 1, mid + 1,right);
    }
    int Query(int left, int right)
    {
        if(left > right)
            return 0;
        left_limit = left;
        right_limit = right;
        elem.clear();
        QueryRange(1,1,n);
        if(elem.empty())
            return 0 ;
        Node ans = elem[0];
        for(int i = 1; i < elem.size();i++)
            ans = merge(ans,elem[i]);
        return ans.val;
    }
    int findtree(int val,int where,int left,int right)
    {
        if(left == right)
        {
            tree[where].val = 0;
            return left;
        }
        int mid = (left + right) / 2;
        int ans;
        if(tree[2*where].val >= val)ans = findtree(val,2*where,left,mid);
        else
            ans =  findtree(val - tree[2*where].val,2*where + 1,mid + 1, right);
        tree[where] = merge(tree[2*where],tree[2*where+1]);
        return ans;
    }

}
int n;
int a[Max];

void read()
{
	f>>n;
	int i;
	for(i=1;i<=n;i++)
		f>>a[i];
}
int clasament[Max];

     

void solve()
{
    SegmentTree::init(1,1,n);
    SegmentTree::n = n;
    int i;
    for(i=n;i>=1;i--)
    {
        int val = a[i];  
        val = SegmentTree::findtree(val,1,1,n);
        clasament[val] = i;
        //SegmentTree::Update(val,1);
    }
    for(i=1;i<=n;i++)
        cout<<clasament[i]<<'\n';
}
void restart()
{

}
int32_t main()
{
   // nos();

        read();
        solve();
        restart();
    
    return 0;
}