Pagini recente » Cod sursa (job #1777686) | Cod sursa (job #724969) | Cod sursa (job #2076411) | Cod sursa (job #1308083) | Cod sursa (job #2610006)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream r("schi.in");
ofstream w("schi.out");
int v[30002], ai[100000], fin[30002], sum;
void update(int poz)
{
ai[poz]=ai[poz*2]+ai[poz*2+1];
if(poz==1)
{
return;
}
else
{
update(poz/2);
}
}
void query(int st, int dr, int a, int b, int nod){
if(st==a && dr==b){
sum+=ai[nod];
}
else{
if(st<=(a+b)/2){
query(st, min(dr, (a+b)/2), a, (a+b)/2, nod*2);
}
if(dr>(a+b)/2){
query(max(st, (a+b)/2+1), dr, (a+b)/2+1, b, nod*2+1);
}
}
}
int main()
{
int n;
r>>n;
for(int i=1;i<=n;i++){
r>>v[i];
}
int dim=1;
while(dim<n)
{
dim*=2;
}
dim--;
for(int i=n;i>0;i--){
int st=v[i], dr=n, mij, p=v[i];
while(st<=dr){
mij=(st+dr)/2;
sum=0;
query(1+dim, mij+dim, dim+1, dim*2+1, 1);
if(sum+v[i]<=mij){
dr=mij-1;
p=mij;
}
else{
st=mij+1;
}
}
fin[p]=i;
ai[p+dim]=1;
update((p+dim)/2);
}
for(int i=1;i<=n;i++){
w<<fin[i]<<"\n";
}
return 0;
}