Mai intai trebuie sa te autentifici.
Cod sursa(job #2008221)
Utilizator | Data | 5 august 2017 19:52:08 | |
---|---|---|---|
Problema | Schi | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.61 kb |
#include<bits/stdc++.h>
using namespace std;
struct nod
{
int st,dr,sz;
unsigned pr;
};
nod nods[(int)3e4+100]={};
void print(int n)
{
if (!n)
return ;
print(nods[n].st);
printf("%d\n",n);
print(nods[n].dr);
}
int update(int n)
{
nods[n].sz=1+nods[nods[n].st].sz+nods[nods[n].dr].sz;
return n;
}
pair<int,int> split(int n,const int nr)
{
if (nr==0)
return make_pair(0,n);
if (nr==nods[n].sz)
return make_pair(n,0);
if (nr>=nods[nods[n].st].sz+1)
{
auto t=split(nods[n].dr,nr-nods[nods[n].st].sz-1);
nods[n].dr=t.first;
return make_pair(update(n),t.second);
}
else
{
auto t=split(nods[n].st,nr);
nods[n].st=t.second;
return make_pair(t.first,update(n));
}
}
int join(int t1,int t2)
{
if (t1==0)
return t2;
if (t2==0)
return t1;
if (nods[t1].pr>nods[t2].pr)
{
nods[t1].dr=join(nods[t1].dr,t2);
return update(t1);
}
else
{
nods[t2].st=join(t1,nods[t2].st);
return update(t2);
}
}
int insert(int n,const int poz,const int val)
{
auto t=split(n,poz);
nods[val].pr=rand();
nods[val].sz=1;
return join(join(t.first,val),t.second);
}
int main()
{
freopen("schi.in","r",stdin);
freopen("schi.out","w",stdout);
int n,i,x;
srand(time(0));
scanf("%d",&n);
int rad=0;
for(i=1;i<=n;i++)
{
scanf("%d",&x);
rad=insert(rad,x-1,i);
}
print(rad);
return 0;
}