Pagini recente » Cod sursa (job #1733446) | Cod sursa (job #1745248) | Cod sursa (job #2814465) | Cod sursa (job #2137195) | Cod sursa (job #3319762)
#include <bits/stdc++.h>
FILE *fin, *fout;
struct Treap{
int idx;
int val;
int priority;
int sz;
Treap *left;
Treap *right;
};
int get_sz(Treap *t) {
if(t == nullptr)
return 0;
return t->sz;
}
void rebuild(Treap *t) {
if(t == nullptr)
return;
t->sz = 1 + get_sz(t->left) + get_sz(t->right);
}
std::pair<Treap*, Treap*> split(Treap* t, int x) {
if(t == nullptr) {
return {nullptr, nullptr};
}else if(get_sz(t->left) >= x) {
auto [first, second] = split(t->left, x);
t->left = second;
rebuild(t);
return {first, t};
}else {
auto[first, second] = split(t->right, x - get_sz(t->left) - 1);
t->right = first;
rebuild(t);
return {t, second};
}
}
Treap* merge(Treap* l, Treap* r) {
if(l == nullptr)
return r;
else if(r == nullptr)
return l;
else if(l->priority > r->priority){
l->right = merge(l->right, r);
rebuild(l);
return l;
}else {
r->left = merge(l, r->left);
rebuild(r);
return r;
}
}
Treap* insert(Treap* t, int poz, int val) {
Treap* nd = new Treap{
.idx = poz,
.val = val,
.priority = rand(),
.sz = 1,
.left = nullptr,
.right = nullptr
};
auto [first, second] = split(t, poz);
return merge(merge(first, nd), second);
}
void dump(Treap *t) {
if(t == nullptr)
return;
rebuild(t);
dump(t->left);
fprintf(fout, "%d\n", t->val);
dump(t->right);
}
int main(){
fin = fopen("schi.in", "r");
fout = fopen("schi.out", "w");
int n;
fscanf(fin, "%d", &n);
Treap *t = nullptr;
for( int i = 0; i < n; i++ ) {
int x;
fscanf(fin, "%d", &x);
x--;
t = insert(t, x, i + 1);
}
dump(t);
fclose(fin);
fclose(fout);
return 0;
}