Cod sursa(job #2955125)

Utilizator PieleVoinescu David Piele Data 16 decembrie 2022 12:42:28
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define nmax 30005

using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

int arb[4*nmax];
int rasp[nmax];
int a[nmax];
int n;

void creez(int nod,int st,int dr,int pos)
{
    if(st==dr)
    {
        arb[nod]=1;
        return;
    }
    int mid=(st+dr)/2;
    if(pos<=mid)
        creez(2*nod,st,mid,pos);
    else creez(2*nod+1,mid+1,dr,pos);
    arb[nod]=arb[2*nod]+arb[2*nod+1];
}

void update(int nod,int st,int dr,int pos,int val)
{
    if(st==dr)
    {
        arb[nod]=0;
        rasp[st]=val;
        return;
    }
    int mid=(st+dr)/2;
    int stangu=2*nod;
    int dreptu=2*nod+1;
    if(pos<=arb[stangu])
            update(stangu,st,mid,pos,val);
    else update(dreptu,mid+1,dr,pos-arb[stangu],val);
    arb[nod]=arb[stangu]+arb[dreptu];
}

void citire()
{
    fin>>n;
    for(int i=1;i<=n;++i){
        fin>>a[i];
        creez(1,1,n,i);
    }
    for(int i=n;i>=1;i--){///coada la fata n -> 1
    update(1,1,n,a[i],i);
    }
    for(int i=1;i<=n;++i)
        fout<<rasp[i]<<'\n';
}

int main()
{
     ios_base::sync_with_stdio(false);
citire();

fin.close();
fout.close();
    return 0;
}