Pagini recente » Cod sursa (job #255394) | Cod sursa (job #241137) | Cod sursa (job #1966500) | Cod sursa (job #1854055) | Cod sursa (job #2861222)
#include "fstream"
#include "iostream"
const int maxSize = 30000, log2MaxSize=15;
int nr=0,sizen=0;
struct Node{
int val=0;
int size=0;
Node *l=nullptr, *r=nullptr, *p=nullptr;
Node(int newval=0, int newsize=0, Node *newl=nullptr, Node *newr=nullptr, Node *newp=nullptr){
val=newval;
size=newsize;
l=newl;
r=newr;
p=newp;
}
void operator+=(int val){
Node *c=this;
while(c){
c->val+=val;
c=c->p;
nr++;
}
}
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 Node::error = Node(-1,-1,nullptr,nullptr,nullptr);
class BinaryPartialSum{
private:
bool initd=false;
void init(Node *c, int l, int r){
sizen++;
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;
int cp = n;
for(n=1;n<cp;n*=2);
peak->size=n;
peak->val=0;
init(peak, 0, n);
initd=true;
}
Node &operator[](int i){
if(!initd||i>=peak->size){
return Node::error;
}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 Node::error;
}
};
int pos[30000],sol[30000];
BinaryPartialSum v(30000);
int main(){
using namespace std;
ifstream in("schi.in");
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";
}