Cod sursa(job #1385672)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 12 martie 2015 11:03:29
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int N,Array[30005],Partial[30005],Poz[30005],Arb[4*30005],Lazy[4*30005];
void Build(int K,int L,int R)
{
    if(L>R)
        return;
    if(L==R)
    {
        Arb[K]=L;
        return;
    }
    Build(2*K,L,(L+R)/2);
    Build(2*K+1,(L+R)/2+1,R);
    Arb[K]=Arb[2*K]+Arb[2*K+1];
}
void Read()
{
    f>>N;
    for(int i=1;i<=N;i++)
        f>>Array[i];
    Build(1,1,N);
}
void Update(int K,int L,int R,int x,int y,int val)
{
    int node=K;
    if(Lazy[node]!=0)
    {
        Arb[node]+=Lazy[node];
        if(L!=R)
        {
            Lazy[2*node]+=Lazy[node];
            Lazy[2*node+1]+=Lazy[node];
        }
        Lazy[node]=0;
    }
    if(L>R || L>y || R<x)
        return;
    if(x<=L && R<=y)
    {
        Arb[K]+=val;
        if(L==R)
            return;
        Lazy[K*2]+=val;
        Lazy[K*2+1]+=val;
        return;
    }
    Update(2*K,L,(L+R)/2,x,y,val);
    Update(2*K+1,(L+R)/2+1,R,x,y,val);
    Arb[K]=Arb[2*K]+Arb[2*K+1];
}
int Query(int K,int L,int R,int x,int y)
{
     int node=K;
    if(Lazy[node]!=0)
    {
        Arb[node]+=Lazy[node];
        if(L!=R)
        {
            Lazy[2*node]+=Lazy[node];
            Lazy[2*node+1]+=Lazy[node];
        }
        Lazy[node]=0;
    }
    if(L>R || L>y || R<x)
        return 0;
    if(x<=L && R<=y)
        return Arb[K];
    int a=Query(K*2,L,(L+R)/2,x,y);
    int b=Query(K*2+1,(L+R)/2+1,R,x,y);
    return a+b;
}
int binSearch(int val)
{
    int mid,sol=0,left=1,right=N;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(Query(1,1,N,mid,mid)>=val)
        {
            sol=mid;
            right=mid-1;
        }
        else
            left=mid+1;
    }
    return sol;
}
void Solve()
{
    for(int i=N;i>=1;i--)
    {
        int poz=binSearch(Array[i]);
        Poz[poz]=i;
        Update(1,1,N,poz,N,-1);
    }
    for(int i=1;i<=N;i++)
        g<<Poz[i]<<"\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}