Cod sursa(job #1837549)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 29 decembrie 2016 21:17:39
Problema Schi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define MAXN 30050

using namespace std;

int n;

struct treap
{
    struct nod
    {
        int inf, w, pri;
        nod *st, *dr;
        nod (int inf = 0, int w = 0, int pri = 0, nod *st = nullptr, nod *dr = nullptr) : inf(inf), w(w), pri(pri), st(st), dr(dr) { }

    };
    void fix(nod *&e)
	{
		e->w = e->st->w + e->dr->w + 1;
	}
	const static int MP = 0x3f3f3f3f;
	nod *root, *nil;
    treap()
    {
		nil = new nod();
        root = nil;
    }

    void rotRight(nod *&crt)
    {
        nod *aux = crt->st;
        crt->st = aux->dr;
        aux->dr = crt;
        fix(crt);
        crt = aux;
        fix(crt);
    }

    void rotLeft(nod *&crt)
    {
        nod *aux = crt->dr;
		crt->dr = aux->st;
        aux->st = crt;
        fix(crt);
        crt = aux;
        fix(crt);
    }

	void add(int pos, int val)
	{
		add(pos, val, root);
	}

	void add(int pos, int val, nod *&crt)
	{
		if (crt == nil)
		{
			crt = new nod(val, 1, (rand())&MP + 1, nil, nil);
			return;
		}
        if (crt->st->w + 1 >= pos)
            add(pos, val, crt->st);
		else
			add(pos-(crt->st->w + 1), val, crt->dr);
        if (crt->st->pri > crt->pri)
			rotRight(crt);
		else if (crt->dr->pri > crt->pri)
			rotLeft(crt);
		fix(crt);
	}

    void print()
    {
		print(root);
    }

    void print(nod *crt)
    {
        if (crt == nil)
			return;
        print(crt->st);
        printf("%d\n", crt->inf);
		print(crt->dr);
    }
};

treap t;

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
	srand(time(0));

    scanf("%d ", &n);
    for (int i = 1; i <= n; i++) {
        int pos;
        scanf("%d", &pos);
        t.add(pos, i);
    }
    t.print();

    return 0;
}