Pagini recente » Cod sursa (job #2645649) | Cod sursa (job #1201446) | Cod sursa (job #1227029) | Cod sursa (job #318028) | Cod sursa (job #2862993)
#include "fstream"
#include "iostream"
namespace containrr{
using namespace containrr;
struct Command{
short command=-1;
long long val=0;
Command(short commandID, long long value=0){
command=commandID;
val=value;
}
};
Command lowerBound(long long val){
return Command(1,val);
}
Command upperBound(long long val){
return Command(2,val);
}
template <class T=int>
class BinaryPartialSum{
private:
long long *dims=nullptr, *powsOf2=nullptr, *modif=nullptr, *currentPos=nullptr, commandValue=0;
T *tree=nullptr;
short dimNR=0,currentPosIndex=0, commandDim=-1, command=-1;
bool checkCurrentPosValidity(){
if(currentPosIndex!=dimNR)
return 0;
for(short i=0;i<dimNR;i++)
if(currentPos[i]>=dims[i])
return 0;
return 1;
}
long long basePos(short dim){
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;
long long i=currentPos[dim], bkp=currentPos[dim], pow=1, base=basePos(dim);
while(i<dims[dim]){
if((i+1)%pow){
currentPos[dim]=i;
if(dim>0){
add(x, dim-1);
}else
tree[base+i]+=x;
i+=pow>>1;
}
pow=pow<<1;
}
currentPos[dim]=bkp;
}
long long get(short dim){
long long pos=currentPos[dim]+1, base=basePos(dim), sum=0;
currentPos[dim]=-1;
for(long long pow=1ll<<powsOf2[dim];pow>0;pow=pow>>1){
if(currentPos[dim]+pow<pos){
currentPos[dim]+=pow;
dim==0 ? sum+=tree[base+currentPos[dim]] : sum+=get(dim-1);
}
}
currentPos[dim]=pos-1;
return sum;
}
void init(){
powsOf2=new long long[dimNR];
modif=new long long[dimNR];
currentPos=new long long[dimNR];
long long factor=1;
for(int i=0;i<dimNR;i++){
modif[i]=factor;
factor*=dims[i];
while((1ll<<powsOf2[i])<=dims[i])
powsOf2[i]++;
powsOf2[i]--;
}
tree = new T[factor];
}
void getDimensions(){
init();
}
template<typename IntType, typename... Types>
void getDimensions(IntType length, Types... lengths){
dims[dimNR++]=length;
getDimensions(lengths...);
}
void getDimNR(){return;}
template<typename IntType, typename... Types>
void getDimNR(IntType length, Types... lengths){
dimNR++;
getDimNR(lengths...);
}
long long getLowerBound(T val){
int i=-1;
long long sum=0;
for(long long pow=1ll<<powsOf2[commandDim];pow>0;pow=pow>>1){
if(i+pow<dims[commandDim]&&sum+tree[i+pow]<val){
i+=pow;
sum+=tree[i];
}
}
return i+1;
}
long long getUpperBound(T val){
currentPos[commandDim]=-1;
for(long long pow=1ll<<powsOf2[commandDim];pow>0;pow=pow>>1){
currentPos[commandDim]+=pow;
if(currentPos[commandDim]>=dims[commandDim]||get(dimNR-1)>=val+1)
currentPos[commandDim]-=pow;
}
return currentPos[commandDim]+1;
}
public:
template<typename... Types>
BinaryPartialSum(Types... lengths){
getDimNR(lengths...);
dims=new long long[dimNR];
dimNR=0;
getDimensions(lengths...);
}
T debugval(T newval=0){
if(newval){
tree[basePos(0)+currentPos[0]]=newval;
return 0;
}
if(checkCurrentPosValidity()){
return tree[basePos(0)+currentPos[0]];
}
return 0;
}
operator long long(){
long long val=0;
if(checkCurrentPosValidity())
switch (command)
{
case 1:
val=getLowerBound(commandValue);
break;
case 2:
val=getUpperBound(commandValue);
break;
default:
val=get(dimNR-1);
break;
}
currentPosIndex=0;
command=-1;
commandDim=-1;
commandValue=0;
return val;
}
BinaryPartialSum &operator[](long long pos) {
currentPos[currentPosIndex++]=pos;
return *this;
}
BinaryPartialSum &operator[](Command command) {
this->command=command.command;
this->commandValue=command.val;
commandDim=currentPosIndex;
currentPos[currentPosIndex++]=0;
return *this;
}
void operator+=(T x){
if(checkCurrentPosValidity())
add(x);
currentPosIndex=0;
}
void operator-=(T x){
if(checkCurrentPosValidity())
add(-x);
currentPosIndex=0;
}
};
}
long long pos[30000],sol[30000];
int main(){
using namespace std;
using namespace containrr;
ifstream in("schi.in");
ofstream out("schi.out");
int n;
in>>n;
BinaryPartialSum<long long> v(n);
for(int i=0;i<n;i++){
in>>pos[i];
v[i]+=1;
}
for(int i=n-1;i>=0;i--){
int currpos=v[lowerBound(pos[i])];
cout<<currpos<<" ";
sol[currpos]=i+1;
v[currpos]-=1;
}
for(int i=0;i<n;i++)
out<<sol[i]<<"\n";
out<<flush;
}