Cod sursa(job #2383410)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 19 martie 2019 14:18:12
Problema Schi Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int v[30005],sol[30005],lazy[30005],sume[30005],i,n,DIM;
void update (int st,int dr,int delta)
{
    int lim_st=((st+DIM-1)/DIM)*DIM;
    int lim_dr=(dr/DIM)*DIM;
    if (lim_st>lim_dr)
    {
        for (int i=st;i<=dr;++i)
        {
            v[i]+=delta;
        }
        sume[lim_dr/DIM]+=(dr-st+1)*delta;
    }
    else
    {
        for (int i=st;i<lim_st;i++)
        {
            v[i]+=delta;
        }
        for (int i=lim_dr;i<=dr;i++)
        {
            v[i]+=delta;
        }
        sume[st/DIM]+=delta*(lim_st-st);
        sume[dr/DIM]+=delta*(dr-lim_dr+1);
        int bucata_st=st/DIM,bucata_dr=dr/DIM;
        for (int i=bucata_st+1;i<bucata_dr;i++)
        {
            lazy[i]+=delta;
            sume[i]+=delta*DIM;
        }
    }
}
int query (int st,int dr)
{
    int lim_st=((st+DIM-1)/DIM)*DIM;
    int lim_dr=(dr/DIM)*DIM;
    int rez=0,i;
    if (lim_st>lim_dr)
    {
        for (i=st;i<=dr;i++)
        {
            rez+=v[i];
        }
        rez+=(dr-st+1)*lazy[st/DIM];
    }
    else
    {
        for (int i=st;i<lim_st;i++)
        {
            rez+=v[i];
        }
        for (int i=lim_dr;i<=dr;i++)
        {
            rez+=v[i];
        }
        rez+=lazy[st/DIM]*(lim_st-st);
        rez+=lazy[dr/DIM]*(dr-lim_dr+1);
        int bucata_st=st/DIM,bucata_dr=dr/DIM;
        for (int i=bucata_st+1;i<bucata_dr;i++)
        {
            rez+=sume[i];
        }
    }
    return rez;
}
int cautarebinara(int x)
{
    int st,dr,mij,minim=99999999,t;
    st=1;
    dr=n;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        t=query(1,mij);
        if (t==x&&mij<minim)
        {
            minim=mij;
        }
        else
        if (t>=x)
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    return minim;
}
int v1[30005],z;
int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    f>>n;
    DIM=sqrt(n);
    for (i=1;i<=n;i++)
    {
        f>>v1[i];
    }
    update(1,n,1);
    for (i=n;i>=1;i--)
    {
        z=cautarebinara(v1[i]);
        sol[z]=i;
        update(z,z,-1);
    }
    for (i=1;i<=n;i++)
    {
        g<<sol[i]<<'\n';
    }
    return 0;
}