Cod sursa(job #2861033)

Utilizator ANicon111Albu Nicon Georgian ANicon111 Data 3 martie 2022 12:55:05
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include "fstream"

const int maxSize = 30000, log2MaxSize=15;

struct Node{
    int val=0;
    int size;
    Node *l=nullptr, *r=nullptr, *p=nullptr;

    void operator+=(int val){
        Node *c=this;
        while(c){
            c->val+=val;
            c=c->p;
        }
    }

    operator int(){
        int sum=val;
        Node *c=this;
        while (c->p){
            if(c==c->p->r)
                sum+=c->p->l->val;
            c=c->p;
        }
        return sum;
    }
    static Node error(){
        Node error;
        error.size=-1;
        return error;
    }
};

class BinaryPartialSum{
    private:
    bool initd=false;

    void init(Node *c, int l, int r){
        if(r-l>1){
            int pow2=1;
            while(pow2<r-l)
                pow2*=2;
            pow2/=2;
            c->l=new Node;
            c->l->size=pow2;
            c->l->val=0;
            c->l->p=c;
            init(c->l, l,l+pow2);
            c->r=new Node;
            c->r->size=r-l-pow2;
            c->r->val=0;
            c->r->p=c;
            init(c->r, l+pow2, r);
        }
    }

    public:
    Node *peak;

    BinaryPartialSum(int n){
        peak=new Node;
        peak->size=n;
        peak->val=0;
        init(peak, 0, n);
        initd=true;
    }

    Node *operator[](int i){
        if(!initd||i>=peak->size){
            return nullptr;
        }else{
            Node *c=peak;
            int pow2=1;
            while(pow2<peak->size)
                pow2*=2;
            pow2/=2;
            while(pow2){
                if(i/pow2==0){
                    c=c->l;
                }else{
                    c=c->r;
                    i-=pow2;
                }
                pow2/=2;
            }
            return c;
        }
        return nullptr;
    }
};

int pos[30000],sol[30000];

int main(){
    std::ifstream in("schi.in");
    std::ofstream out("schi.out");
    int n;
    in>>n;
    BinaryPartialSum 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+=int(*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";
}