Pagini recente » Cod sursa (job #2750071) | Cod sursa (job #1568562) | Cod sursa (job #1440899) | Cod sursa (job #1993156) | Cod sursa (job #829381)
Cod sursa(job #829381)
#include <fstream>
#define LS (current_position<<1)
#define RS (current_position<<1)+1
#define INF (1<<20)
#define NMAX 61002
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
int N,begin,end,value;
int C[30002];
struct my_struct{int add,nr;}V[NMAX];
void Update(int current_position,int start,int final)
{
if(start>=begin && final <=end)
V[current_position].add +=value;
else
{
int med = (start + final) / 2;
if(begin<=med)
Update(LS,start,med);
if(med+1<=end)
Update(RS,med+1,final);
if(C[V[LS].nr]+V[LS].add<C[V[RS].nr]+V[RS].add)
V[current_position].nr = V[LS].nr,V[current_position].add+=V[LS].add;
else V[current_position].nr = V[RS].nr,V[current_position].add+=V[RS].add;
}
}
void Refresh(int current_position,int start,int final)
{
if(start == final);
else
{
int med = (start + final) / 2;
Refresh(LS,start,med);
Refresh(RS,med+1,final);
if(C[V[LS].nr]+V[LS].add<C[V[RS].nr]+V[RS].add)
V[current_position].nr = V[LS].nr,V[current_position].add+=V[LS].add;
else V[current_position].nr = V[RS].nr,V[current_position].add+=V[RS].add;
}
}
int main()
{
int i,x;
in>>N;
for(i=1;i<=N;i++)
in>>C[i],V[N+i-1].nr = i;
Refresh(1,1,N);
for(i=0;i<NMAX;i++)
V[i].nr = INF,V[i].add = INF;
return 0;
for(i=1;i<=N;i++)
{
out<<(x = V[1].nr)<<'\n';
begin = x,end = x,value = INF;
Update(1,1,N);
begin = 1,end = x,value = 1;
Update(1,1,N);
}
return 0;
}