Cod sursa(job #2785910)

Utilizator Iulia_DianaIulia Diana Iulia_Diana Data 19 octombrie 2021 20:12:38
Problema Schi Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int arbint[120005], n, pozitii[30005];
int cauta(int st, int dr, int nod, int l, int r)
{
    if(l>dr || r<st)   return 0;
    if(st>=l && dr<=r)  return arbint[nod];
    int mij=(st+dr)/2, rez1, rez2;
    rez1=cauta(st, mij, nod*2, l, r);
    rez2=cauta(mij+1, dr, nod*2+1, l, r);
    return rez1+rez2;

}
void update(int st, int dr, int nod, int poz)
{
    if(st==dr && st==poz)
    {
        arbint[nod]++;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)  update(st, mij, nod*2, poz);
    else  update(mij+1, dr, nod*2+1, poz);
    arbint[nod]=arbint[nod*2]+arbint[nod*2+1];
}
int main()
{
    fin >> n;
    vector <int> v(n+5);
    for(int i=1; i<=n; i++)   fin >> v[i];
    for(int i=n; i>0; i--)
    {
        int a=0, st=1, dr=n;
        while(st<=dr && a==0)
        {
            int mij=(st+dr)/2, aux;
            aux=cauta(1, n, 1, 1, mij);
            if(mij-aux==v[i] && pozitii[mij]==0)  a=mij;
            else
                if(mij-aux<v[i])  st=mij+1;
            else dr=mij-1;
        }
        pozitii[a]=i;
        update(1, n, 1, a);
    }
    for(int i=1; i<=n; i++)   fout << pozitii[i] << "\n";
    return 0;
}