Cod sursa(job #2862287)

Utilizator ANicon111Albu Nicon Georgian ANicon111 Data 5 martie 2022 11:09:05
Problema Schi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.45 kb
#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],antpos=pos[i];
        currpos+=v[currpos];
        v[currpos]+=1;
        while(sol[currpos]!=0){
            int temp=currpos;
            currpos+=v[currpos]-v[antpos];
            antpos=temp;
        }
        sol[currpos]=i+1;
    }
    for(int i=0;i<n;i++)
        out<<sol[i]<<"\n";
    out<<flush;
}