Cod sursa(job #2020398)

Utilizator sergiudnyTritean Sergiu sergiudny Data 10 septembrie 2017 01:25:05
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>
#define DM 30005
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

int segmTree[4*DM],v[DM],rez[DM],n;

void updateTree(int nod,int st,int dr,int poz,int val){
    if(st==dr){
        segmTree[nod]=val;
        return;
    }
    int mid=(st+dr)/2,fs=2*nod;

    if(poz>mid) updateTree(fs+1,mid+1,dr,poz,val);
    else updateTree(fs,st,mid,poz,val);

    segmTree[nod]=segmTree[fs]+segmTree[fs+1];
}

void getVal(int nod,int st,int dr,int poz,int val){
    if(st==dr){
        rez[st]=val,segmTree[nod]=0;
        return;
    }
    int mid=(st+dr)/2,fs=2*nod;
    if(segmTree[fs]>=poz)
        getVal(fs,st,mid,poz,val);
    else
        getVal(fs+1,mid+1,dr,poz-segmTree[fs],val);

    segmTree[nod]=segmTree[fs]+segmTree[fs+1];
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;++i)
        fin>>v[i],updateTree(1,1,n,i,1);
    for(int i=n;i;--i)
        getVal(1,1,n,v[i],i);
    for(int i=1;i<=n;++i)
        fout<<rez[i]<<'\n';
    return 0;
}