Pagini recente » Cod sursa (job #1142679) | Cod sursa (job #295070) | Cod sursa (job #1359817) | Cod sursa (job #1516239) | Cod sursa (job #2861033)
#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";
}