Cod sursa(job #3290072)

Utilizator wiki__Andrei Alecu izsak wiki__ Data 29 martie 2025 12:42:04
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <set>
#include <vector>
#include <bitset>
#include <map>
#include <climits>
#pragma GCC optimize("O3,Ofast,unroll-loops")
using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

const int NMAX = 30005;
int Tree[NMAX*4],v[NMAX],n;

void Build(int st,int dr,int node) {
    if (st == dr) {
        Tree[node] = 1;
        return;
    }
    int mid = (st + dr) / 2;
    Build(st,mid,node*2);
    Build(mid+1,dr,node*2+1);
    Tree[node] = Tree[node*2] + Tree[node*2+1];
}

void Update(int st,int dr,int node,int p,int x) {
    if (st == dr) {
        Tree[node] = x;
        return;
    }
    int mid = (st + dr) / 2;
    if (p <= mid) {
        Update(st,mid,node*2,p,x);
    }
    else {
        Update(mid+1,dr,node*2+1,p,x);
    }
    Tree[node] = Tree[node*2] + Tree[node*2+1];
}

int querry(int st,int dr,int node,int x) {
    if (st == dr) {
        return st;
    }
    int mid = (st + dr) / 2;
    if (Tree[node*2] >= x) {
        return querry(st,mid,node*2,x);
    } 
    else {
        x -= Tree[node*2];
        return querry(mid+1,dr,node*2+1,x);
    }
}

int ans[NMAX];

int main() {

    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>v[i];
    }
    Build(1,n,1);

    for (int i=n; i>=1; i--) {
        int x = querry(1,n,1,v[i]);
        ans[x] = i;
        Update(1,n,1,x,0);
    }

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

}