Pagini recente » Cod sursa (job #3140271) | Cod sursa (job #402273) | Rating francydarkcool (c909010) | Cod sursa (job #1187792) | Cod sursa (job #1308061)
#include<cstdio>
#include<time.h>
#include<cstdlib>
using namespace std;
const int N = 30100;
struct t {
int k, nrel;
int p;
t *f1, *f2;
t() {
k = p = 0;
nrel = 0;
}
t(int a, int b, t *c, t *d) {
k = a; p = b;
f1 = c; f2 = d;
nrel = 1;
}
};
class treap {
public:
t *rad, *nil;
treap() {
nil = new t;
nil->f1 = nil->f2 = nil;
rad = nil;
}
void rotLeft(t* &r) {
t *temp = r->f1;
r->f1 = temp->f2;
temp->f2 = r;
r = temp;
}
void rotRight(t* &r) {
t *temp = r->f2;
r->f2 = temp->f1;
temp->f1 = r;
r = temp;
}
void recalc(t* &r) {
if(r != nil)
r->nrel = 1 + r->f1->nrel + r->f2->nrel;
}
void balance(t* &r) {
if(r->f2->p > r->p)
rotRight(r);
if(r->f1->p > r->p)
rotLeft(r);
recalc(r->f1);
recalc(r->f2);
recalc(r);
}
void update(t* &r, int key, int val, int pri) {
if(r == nil) {
r = new t(key, pri, nil, nil);
return;
}
if(r->f1->nrel < val)
update(r->f2, key, val - (r->f1->nrel) - 1, pri);
else
update(r->f1, key, val, pri);
balance(r);
}
void update(int key, int val) {
update(rad, key, val, rand()%20000000 + 1);
}
void print(t* &r) {
if(r == nil)
return;
print(r->f1);
printf("%d\n", r->k);
print(r->f2);
}
void print() {
print(rad);
}
};
int n;
treap t;
int main() {
freopen("schi.in", "r", stdin);
freopen("schi.out", "w", stdout);
int i;
srand(777);
int x;
scanf("%d", &n);
for(i = 1; i <= n; ++i) {
scanf("%d", &x);
t.update(i, x - 1);
}
t.print();
return 0;
}