Pagini recente » Cod sursa (job #1892352) | Cod sursa (job #93985) | Cod sursa (job #304643) | Cod sursa (job #1726368) | Cod sursa (job #2862272)
#include "fstream"
#include "iostream"
template <class T=int, class Max=long long>
class BinaryPartialSum{
private:
unsigned long long *dims=nullptr, *powsOf2=nullptr, *modif=nullptr, *currentPos=nullptr;
T *tree=nullptr;
short dimNR=0,currentPosIndex=0;
bool checkCurrentPosValidity(){
if(currentPosIndex!=dimNR)
return 0;
for(short i=0;i<dimNR;i++)
if(currentPos[i]>=dims[i])
return 0;
return 1;
}
unsigned long long basePos(short dim){
unsigned long long sum=0;
for(short i=dimNR-1;i>dim;i--)
sum+=modif[i]*currentPos[i];
return sum;
}
void add(T x, short dim=-1){
if(dim==-1)
dim=dimNR-1;
unsigned long long i=currentPos[dim], bkp=currentPos[dim], pow=1;
while(i<dims[dim]){
if((i+1)%pow){
currentPos[dim]=i;
if(dim>0){
add(x, dim-1);
}else
tree[basePos(dim)+i]+=x;
i+=pow>>1;
}
pow=pow<<1;
}
currentPos[dim]=bkp;
}
Max get(short dim=-1){
if(dim==-1)
dim=dimNR-1;
unsigned long long i=0, pow=1<<powsOf2[dim], pos=currentPos[dim]+1;
Max sum=0;
while(pow>pos)
pow=pow>>1;
while(pow){
if(i+pow<=pos){
i+=pow;
if(dim==0)
sum+=tree[basePos(dim)+i-1];
else{
currentPos[dim]=i-1;
sum+=get(dim-1);
}
}
if(pow==0)
i++;
pow=pow>>1;
}
return sum;
}
void init(unsigned long long newn[], short elemNR){
dimNR=elemNR;
dims=new unsigned long long[dimNR];
powsOf2=new unsigned long long[dimNR];
modif=new unsigned long long[dimNR];
currentPos=new unsigned long long[dimNR];
unsigned long long factor=1;
for(int i=0;i<dimNR;i++){
modif[i]=factor;
factor*=newn[i];
dims[i]=newn[i];
while((1<<powsOf2[i])<dims[i])
powsOf2[i]++;
}
tree = new T[factor];
}
public:
void memDump(short dim=-1){
using namespace std;
if(dim==-1){
dim=dimNR-1;
}
if(dim>0){
for(int i=0;i<dims[dim];i++){
currentPos[dim]=i;
memDump(dim-1);
cout<<"\n";
}
}else{
for(int i=0;i<dims[dim];i++)
cout<<tree[basePos(dim)+i]<<" ";
}
currentPos[dim]=0;
if(dim==dimNR-1){
cout<<"\n";
}
}
BinaryPartialSum(unsigned long long newn){
init(&newn, 1);
}
BinaryPartialSum(unsigned long long newn[], unsigned long long length){
init(newn, length);
}
BinaryPartialSum(unsigned int newn[], unsigned long long length){
unsigned long long ullnewn[length];
for(int i=0;i<length;i++)
ullnewn[i]=newn[i];
init(ullnewn, length);
}
BinaryPartialSum(unsigned short newn[], unsigned long long length){
unsigned long long ullnewn[length];
for(int i=0;i<length;i++)
ullnewn[i]=newn[i];
init(ullnewn, length);
}
BinaryPartialSum(long long newn[], unsigned long long length){
unsigned long long ullnewn[length];
for(int i=0;i<length;i++)
ullnewn[i]=newn[i]<0?-newn[i]:newn[i];
init(ullnewn, length);
}
BinaryPartialSum(int newn[], unsigned long long length){
unsigned long long ullnewn[length];
for(int i=0;i<length;i++)
ullnewn[i]=newn[i]<0?-newn[i]:newn[i];
init(ullnewn, length);
}
BinaryPartialSum(short newn[], unsigned long long length){
unsigned long long ullnewn[length];
for(int i=0;i<length;i++)
ullnewn[i]=newn[i]<0?-newn[i]:newn[i];
init(ullnewn, length);
}
operator Max(){
Max val=0;
if(checkCurrentPosValidity())
val=get();
currentPosIndex=0;
return val;
}
BinaryPartialSum &operator[](unsigned long long pos) {
currentPos[currentPosIndex++]=pos;
return *this;
}
void operator+=(T x){
if(checkCurrentPosValidity())
add(x);
currentPosIndex=0;
}
void operator-=(T x){
if(checkCurrentPosValidity())
add(-x);
currentPosIndex=0;
}
void operator=(T x){
if(checkCurrentPosValidity()){
if(currentPos[0]==0)
x-=get(currentPos[0]);
else
x-=get(currentPos[0])-get(currentPos[0]-1);
add(x);
}
currentPosIndex=0;
}
};
long long pos[30000],sol[30000];
int main(){
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
int n;
in>>n;
BinaryPartialSum<long long, long long> v(n);
for(int i=0;i<n;i++){
in>>pos[i];
pos[i]-=1;
}
for(int i=n-1;i>=0;i--){
int currpos=pos[i];
currpos+=v[currpos];
while(sol[currpos]!=0)
currpos+=1;
sol[currpos]=i+1;
v[pos[i]]+=1;
}
for(int i=0;i<n;i++)
out<<sol[i]<<"\n";
out<<flush;
}