Pagini recente » Cod sursa (job #1555210) | Cod sursa (job #348065) | Cod sursa (job #5541) | Cod sursa (job #2855555) | Cod sursa (job #2802973)
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n;
mt19937 my_rand(time(NULL));
struct Node
{
Node *st, *dr;
int val, prior, sz;
};
Node nil;
Node *Treap = &nil;
Node *mod_fiu(Node *nod, int care, Node *son)
{
if(!care)
{
nod->st = son;
}
else
{
nod->dr = son;
}
nod->sz = nod->st->sz + 1 + nod->dr->sz;
return nod;
}
Node *join(Node *st, Node *dr)
{
if(st==&nil)
{
return dr;
}
if(dr==&nil)
{
return st;
}
if(st->prior>=dr->prior)
{
return mod_fiu(st,1,join(st->dr,dr));
}
return mod_fiu(dr,0,join(st,dr->st));
}
pair<Node*,Node*> split(Node *nod, int k)
{
if(nod==&nil)
{
return {&nil,&nil};
}
if(nod->st->sz>=k)
{
auto t = split(nod->st,k);
return {t.first,mod_fiu(nod,0,t.second)};
}
auto t = split(nod->dr,k - nod->st->sz-1);
return {mod_fiu(nod,1,t.first),t.second};
}
void Add(int poz, int val)
{
auto t = split(Treap,poz-1);
Treap = join(join(t.first,new Node{&nil,&nil,val,my_rand(),1}),t.second);
}
int get_val(int poz)
{
auto t = split(Treap,poz-1);
auto t2 = split(t.second,1);
int rez = t2.first->val;
Treap = join(t.first,join(t2.first,t2.second));
return rez;
}
int main()
{
f>>n;
for(int i=1; i<=n; i++)
{
int poz;
f>>poz;
Add(poz,i);
}
for(int i=1; i<=n; i++)
{
g<<get_val(i)<<'\n';
}
return 0;
}