Pagini recente » Cod sursa (job #66350) | Cod sursa (job #1020197) | Cod sursa (job #876000) | Cod sursa (job #2596813) | Cod sursa (job #2383410)
#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;
}