Cod sursa(job #968983)

Utilizator stefanzzzStefan Popa stefanzzz Data 3 iulie 2013 10:44:45
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#define MAXN 30005
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");

int n,v[MAXN],poz[MAXN],aib[MAXN],x,st,dr,mij,qur;

void update(int a);
int query(int a);

int main()
{
    int i;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    for(i=1;i<=n;i++)
        aib[i]=(i&(-i));
    for(i=n;i>=1;i--){
        x=v[i];
        st=1;dr=n;
        while(1){
            mij=(st+dr)/2;
            qur=query(mij);
            if(qur<x)
                st=mij+1;
            else{
                if(qur==x&&!poz[mij])
                    break;
                dr=mij-1;}}
        poz[mij]=i;
        update(mij);}
    for(i=1;i<=n;i++)
        g<<poz[i]<<'\n';
    f.close();
    g.close();
    return 0;
}

void update(int a){
    for(a;a<=n;a+=(a&(-a)))
        aib[a]--;}

int query(int a){
    int S=0;
    for(a;a>0;a-=(a&(-a)))
        S+=aib[a];
    return S;}