Cod sursa(job #1808820)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 18 noiembrie 2016 10:42:13
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<bits/stdc++.h>
#define zeros(i) (i&(-i))
#define maxN 30005
using namespace std;
int n;
int AIB[maxN],v[maxN],pos[maxN];
void update(int pos,int x)
{
    for(int i=pos;i<=n;i+=zeros(i))
    {
        AIB[i]+=x;
    }
}
int query(int pos)
{
    int s=0;
    for(int i=pos;i>=1;i-=zeros(i))
    {
        s+=AIB[i];
    }
    return s;
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    for(int i=n;i>=1;i--)
    {
        int x=query(v[i]);
        int y=v[i]+x;
        while(pos[y])
        {
            y=v[i]+query(y);

        }
                    pos[y]=i;
        update(v[i]+x,1);
    }
    for(int i=1;i<=n;i++) printf("%d\n",pos[i]);
    return 0;
}