Cod sursa(job #3134149)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 28 mai 2023 16:31:20
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
#include<random>
#include<ctime>
using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

mt19937 rng(time(nullptr));

struct nod
{
    int id,p,sz; nod *c[2];
    nod(int &g) : id(g),p(rng()),sz(1) {c[0] = NULL,c[1] = NULL;}
};

int size(nod *& treap){return treap ? treap->sz : 0;}

void split(nod *r,nod *&st,nod *&dr,int &x,int cheie)
{
    if(!r) st = NULL,dr = NULL;
    else
        {
            cheie += size(r->c[0]);
            if(cheie <= x) split(r->c[1],r->c[1],dr,x,cheie + 1),st = r;
            else split(r->c[0],st,r->c[0],x,cheie - size(r->c[0])),dr = r;
            r->sz = 1 + size(r->c[0]) + size(r->c[1]);
        }
}

void merge(nod *&r,nod *st,nod *dr)
{
    if(!st || !dr) r = st ? st : dr;
    else
    {
        if(st->p < dr->p) merge(st->c[1],st->c[1],dr),r = st;
        else merge(dr->c[0],st,dr->c[0]),r = dr;
        r->sz = 1 + size(r->c[0]) + size(r->c[1]);
    }
}

ostream &operator<<(ostream &out,nod *&a)
{
    if(a->c[0]) out << a->c[0];
    out << a->id << '\n';
    if(a->c[1]) out << a->c[1];
    return out;
}

int main()
{
    int n,a; cin >> n; nod *treap = nullptr;
    for(int i = 1; i <= n ; i++)
        {
            cin >> a; a -= 2; nod *st = NULL,*dr = NULL;
            split(treap,st,dr,a,0);
            merge(st,st,new nod(i)); merge(treap,st,dr);
        }

    cout << treap;
    return 0;
}