Pagini recente » Cod sursa (job #133228) | Cod sursa (job #2325951) | Cod sursa (job #697278) | Cod sursa (job #694402) | Cod sursa (job #3156829)
#include <bits/stdc++.h>
#ifdef LOCAL
#define in cin
#define out cout
#endif
using namespace std;
#ifndef LOCAL
ifstream in("schi.in");
ofstream out("schi.out");
#endif
const int nmax = 30005;
struct aint
{
int nxtp2(int n)
{
int p=1;
while(p<n)p*=2;
return p;
}
int offset;
int *data;
aint(int n)
{
offset=nxtp2(n);
data=new int[offset*2];
for(int i=0;i<offset*2;i++)data[i]=0;
init(0,offset-1,1);
}
void init(int st,int dr,int node)
{
if(st==dr)
{
data[node]=1;
return;
}
int mid=(st+dr)/2;
init(st,mid,node*2);
init(mid+1,dr,node*2+1);
data[node]=data[node*2]+data[node*2+1];
}
void update(int poz)
{
data[offset+poz]=0;
for(poz=(poz+offset)/2;poz>0;poz/=2)data[poz]=data[poz*2]+data[poz*2+1];
}
int _cb(int l,int x,int &sum,int st,int dr,int node)
{
if(dr<l)return dr;
if(l<=st&&data[node]+sum<x)
{
sum+=data[node];
return dr;
}
if(st==dr)return st-1;
int mij=(st+dr)/2;
int ras=_cb(l,x,sum,st,mij,node*2);
if(ras<mij)return ras;
if(ras==mij)return _cb(l,x,sum,mij+1,dr,node*2+1);
return 0;
}
int cb(int x)
{
int sum=0;
return _cb(0,x,sum,0,offset-1,1);
}
void debug()
{
cerr<<data[1]<<'\n';
cerr<<data[2]<<' '<<data[3]<<'\n';
cerr<<data[4]<<' '<<data[5]<<' '<<data[6]<<' '<<data[7]<<'\n';
cerr<<data[8]<<' '<<data[9]<<' '<<data[10]<<' '<<data[11]<<' '<<data[12]<<' '<<data[13]<<' '<<data[14]<<' '<<data[15]<<'\n';
}
};
int ans[nmax];
int main()
{
int n;in>>n;
aint root=aint(n);
vector<int> v;
for(int i=0;i<n;i++)
{
int nr;in>>nr;
v.push_back(nr);
}
for(int i=n-1;i>=0;i--)
{
//cerr<<v[i]<<"->";
int rez = root.cb(v[i]);
rez++;
//cerr<<rez<<'\n';
root.update(rez);
//root.debug();
ans[rez+1]=i+1;
}
for(int i=1;i<=n;i++)
{
out<<ans[i]<<'\n';
}
}