Pagini recente » Cod sursa (job #2178651) | Cod sursa (job #2090677) | Cod sursa (job #1359083) | Cod sursa (job #3270848) | Cod sursa (job #226134)
Cod sursa(job #226134)
#include <fstream>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
class Treap {
private:
class Node {
public:
short int key, cnt, pr;
Node *left, *right;
Node(const int &_key) {
key = _key, cnt = 1, pr = rand() % 31013;
left = right = NULL;
}
};
void insert(Node *&, Node *const &, const int &);
int recount(Node *const &) const;
void rotleft(Node *&);
void rotright(Node *&);
void balance(Node *&);
void write(Node *const &) const;
public:
Node *root;
Treap(): root(NULL) {
srand(time(0));
}
void insert(const int &key, const int &pos) {
Node *p = new Node(key);
insert(root, p, pos);
}
void write() const {
write(root);
}
};
void Treap::insert(Node *&p, Node *const &q, const int &pos) {
if(p == NULL) {
p = q;
return;
}
int t = (p->left == NULL ? 0 : p->left->cnt);
if(pos <= t + 1)
insert(p->left, q, pos);
else
insert(p->right, q, pos - t - 1);
balance(p);
}
int Treap::recount(Node *const &p) const {
return 1 + (p->left == NULL ? 0 : p->left->cnt) + (p->right == NULL ? 0 : p->right->cnt);
}
void Treap::rotleft(Node *&p) {
Node *q = p->right;
p->right = q->left, q->left = p;
p->cnt = recount(p), q->cnt = recount(q);
p = q;
}
void Treap::rotright(Node *&p) {
Node *q = p->left;
p->left = q->right, q->right = p;
p->cnt = recount(p), q->cnt = recount(q);
p = q;
}
void Treap::balance(Node *&p) {
if(p->left && p->pr < p->left->pr)
rotright(p);
else
if(p->right && p->pr < p->right->pr)
rotleft(p);
else
p->cnt = recount(p);
}
void Treap::write(Node *const &p) const {
if(!p)
return;
write(p->left);
out << p->key << '\n';
write(p->right);
}
int main() {
int N, pos;
Treap T;
in >> N;
for(int i = 1; i <= N; ++i) {
in >> pos;
T.insert(i, pos);
}
T.write();
return 0;
}