Mai intai trebuie sa te autentifici.

Cod sursa(job #2008221)

Utilizator mari2001Maria Ionescu mari2001 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;
}