Pagini recente » Cod sursa (job #884020) | Rating Byca Blar (bYca3) | Cod sursa (job #1947066) | Istoria paginii planificare/sedinta-20091126 | Cod sursa (job #3163840)
#include <fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
const int Nmax = 30005;
int n,aib[4*Nmax],aint[4*Nmax];
void update_aib(int x, int y){
for(int i=x;i<=n;i+=(i&(-i)))
aib[i]+=y;
}
int query(int x){
if(x == 0)
return Nmax;
int s = 0;
for(int i=x;i>0;i-=(i&(-i)))
s+=aib[i];
return s;
}
bool check(int a, int b){
if(a == 0)
return 0;
if(b == 0)
return 1;
int i = query(a), j = query(b);
if(i<j || (i == j && a>b))
return 1;
return 0;
}
void build(int node, int st, int dr){
if(st == dr){
aint[node] = st;
return;
}
int mid = (st+dr)/2;
build(node+node, st, mid);
build(node+node+1, mid+1, dr);
if(check(aint[node+node], aint[node+node+1]))
aint[node] = aint[node+node];
else
aint[node] = aint[node+node+1];
}
void update(int node, int st, int dr, int x){
if(st == dr){
aint[node] = 0;
return;
}
int mid = (st+dr)/2;
if(x<=mid)
update(node+node, st, mid, x);
else
update(node+node+1, mid+1, dr, x);
if(check(aint[node+node], aint[node+node+1]))
aint[node] = aint[node+node];
else
aint[node] = aint[node+node+1];
}
int main()
{
int p,c,i;
fin >> n;
p = 0;
for(i=1;i<=n;i++){
fin >> c;
update_aib(i,c-p);
p = c;
}
build(1,1,n);
for(i=1;i<=n;i++){
int x = aint[1];
fout << x << '\n';
update(1,1,n,x);
}
return 0;
}