Cod sursa(job #3153828)

Utilizator petric_mariaPetric Maria petric_maria Data 1 octombrie 2023 14:22:44
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,i,v[200005],a[200005],p,x,sol[200005];
int vrf(int val,int stn,int drn,int indn){
    if(stn==drn) return indn-p+1;
    int y;
    if(val<=a[2*indn]) y=vrf(val, stn, (stn+drn)/2, indn*2);
    else  y=vrf(val-a[2*indn], (stn+drn)/2+1, drn, indn*2+1);
    return y;
}
void update1(int poz,int val){
    a[poz]-=val;
    while(poz>=1){
        poz/=2;
        a[poz]=a[poz*2]+a[poz*2+1];
    }
}
void update2(int poz, int val, int stn,int drn, int indn){
    if(stn==drn) a[stn]-=val;
    else{
        if(poz<=(stn+drn)/2) update2(poz, val, stn, (stn+drn)/2, indn*2);
        else  update2(poz, val, (stn+drn)/2+1, drn, indn*2+1);
        a[poz]=a[poz*2]+a[poz*2+1];
    }
}
int main()
{
    f>>n;
    p=1;
    while(p<n) p*=2;
    for(i=1;i<=n;++i) f>>v[i],a[p+i-1]=1;
    for(i=p-1;i>=1;--i) a[i]=a[i*2]+a[i*2+1];
    for(i=n;i>=1;--i){
        x=vrf(v[i],1,n,1);
        sol[x]=i;
        update1(x+p-1,1);
    }
    for(i=1;i<=n;++i) g<<sol[i]<<'\n';
    return 0;
}