Cod sursa(job #3171502)

Utilizator matei8787Matei Dobrea matei8787 Data 18 noiembrie 2023 23:18:51
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
const int N = 3e4;
int aint[4*N];
int n;
vector<int> q;
int fs(int i){ return i * 2; }
int fd(int i){ return i * 2 + 1; }
void build(int nod, int st, int dr)
{
    if ( st == dr )
    {
        aint[nod] = 1;
        return;
    }
    int mij = ( st + dr ) / 2;
    build(fs(nod), st, mij);
    build(fd(nod), mij + 1, dr);
    aint[nod] = aint[fs(nod)] + aint[fd(nod)];
}
void citire()
{
    in>>n;
    for ( int i = 1 ; i <= n ; i++ )
    {
        int x;
        in>>x;
        q.push_back(x);
    }
}
int query(int nod, int st, int dr, int x)
{
    if ( st == dr )
    {
        aint[nod] = 0;
        return st;
    }
    int mij = ( st + dr ) / 2;
    int aux;
    if ( x <= aint[fs(nod)] )
    {
        aux = query(fs(nod), st, mij, x);
    }
    else
    {
        aux = query(fd(nod), mij + 1, dr, x - aint[fs(nod)]);
    }
    aint[nod] = aint[fs(nod)] + aint[fd(nod)];
    return aux;
}
void rez()
{
    reverse(q.begin(), q.end());
    build(1, 1, n);
    vector<int> ans(n+1);
    for ( int i = 0 ; i < q.size() ; i++ )
    {
        int idk = q[i];
        int plm = query(1, 1, n, q[i]);
        ans[plm] = n - i;
    }
    for ( int i = 1 ; i <= n; i++ )
    {
        out<<ans[i]<<'\n';
    }
}
int main()
{
    citire();
    rez();
    return 0;
}