Cod sursa(job #1808835)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 18 noiembrie 2016 11:17:14
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<bits/stdc++.h>
#define zeros(i) (i&(-i))
#define maxN 30005
#define INF INT_MAX
using namespace std;
int n,sol;
int A[4*maxN+5],v[maxN],pos[maxN],AIB[maxN];
void update2(int pos,int x)
{
    for(int i=pos;i<=n;i+=zeros(i)) AIB[i]+=x;
}
int query2(int pos)
{
    int s=0;
    for(int i=pos;i>=1;i-=zeros(i)) s+=AIB[i];
    return s;
}
//In Arbore retinem prima pozitie neocupata din intervalul [st,dr]
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        A[nod]=st;
    }
        else
    {
        int mid=(st+dr)>>1;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        A[nod]=min(A[2*nod],A[2*nod+1]);
    }
}
//update-ocupa o pozitie in Arbore
void update(int nod,int st,int dr,int pos)
{
    if(st==dr)
    {
        A[nod]=INF;
    }
        else
    {
        int mid=(st+dr)>>1;
        if(pos<=mid) update(2*nod,st,mid,pos);
            else update(2*nod+1,mid+1,dr,pos);
        A[nod]=min(A[2*nod],A[2*nod+1]);
    }
}
//prima pozitie libera din intervalul [a,b]
void query(int nod,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
    {
        sol=min(sol,A[nod]);
    }
        else
    {
        int mid=(st+dr)>>1;
        if(a<=mid) query(2*nod,st,mid,a,b);
        if(b>mid) query(2*nod+1,mid+1,dr,a,b);
    }
}
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]);
    }
    build(1,1,n);
    for(int i=n;i>=1;i--)
    {
        sol=INF;
        int y=query2(v[i]);
        v[i]+=y;
        query(1,1,n,v[i],n);
        pos[sol]=i;
        update(1,1,n,sol);
        update2(sol,1);
    }
    for(int i=1;i<=n;i++) printf("%d\n",pos[i]);
    return 0;
}