Cod sursa(job #3259910)

Utilizator PudakPudak Nurberdiyev Pudak Data 28 noiembrie 2024 15:05:03
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

string nume="schi";
ifstream in(nume+".in");
ofstream out(nume+".out");
#define cin in
#define cout out

const int MN=3e5+5;

int arb[MN*4];
int n;

//classic segment tree of the sum
void update(int nod,int st, int dr,int poz, int x)
{
    if(st==dr){
        arb[nod]+=x;
        return;
    }

    nod*=2;
    int mid=(st+dr)/2;

    if(poz<=mid)update(nod,st,mid,poz,x);
    else update(nod+1, mid+1,dr,poz,x);

    arb[nod>>1]=arb[nod]+arb[nod+1];
}

/*
    Query returns an available index.
    query returns between all available positions which
    val'th position will be. For ex if available indexes are
    1, 4, 6, 7, 8 and val=3, then query will return 6.
    Because 6 is 3rd available slot.
*/
int query(int nod, int st, int dr,int val)
{
    if(st==dr) return st;

    int mid=(st+dr)/2;
    nod*=2;

    //If not enough available slots are on the left then we must search on the RIGHT
    if(arb[nod]<val) return query(nod+1,mid+1,dr,val-arb[nod]);

    //if searched val is enough on the left then go LEFT
    return query(nod,st,mid,val);
}

int v[MN];
int ans[MN];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        update(1,1,n,i,1);
    }

    //start from the end because it will be computed for sure
    for(int i=n;i>=1;i--){
        //get the available slot for v[i]
        int poz=query(1,1,n,v[i]);

        //mark available slot at poz as ZERO
        //so that position cannot be taken afterward by other players
        update(1,1,n,poz, -1);

        //mark poz as i because i'th player is at rank poz
        ans[poz]=i;
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<'\n';

    return 0;
}