Cod sursa(job #2802973)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 19 noiembrie 2021 10:21:59
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#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;
}