Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fs first
- #define sc second
- using namespace std;
- const int INF = 1e9 + 228;
- const int max_n = 1e5 + 228;
- struct Treap {
- int x, y;
- int sz, mn;
- Treap *l, *r;
- Treap (int _x) {
- sz = x = mn = _x;
- y = rand();
- l = nullptr;
- r = nullptr;
- }
- };
- int Size(Treap* t) {
- if (t == nullptr) {
- return 0;
- }
- return t->sz;
- }
- int Minn(Treap* t) {
- if (t == nullptr) {
- return INF;
- }
- return t->mn;
- }
- pair <Treap*, Treap*> Split(Treap* t, int k) {
- if (t == nullptr) {
- return {nullptr, nullptr};
- }
- if (k == 0) {
- return {nullptr, t};
- }
- int ls = Size(t->l);
- if (ls >= k) {
- pair <Treap*, Treap*> p = Split(t->l, k);
- t->l = p.sc;
- t->sz = Size(t->l) + Size(t->r) + 1;
- t->mn = min(min(Minn(t->l), Minn(t->r)), t->x);
- return {p.fs, t};
- } else {
- pair <Treap*, Treap*> p = Split(t->r, k - ls - 1);
- t->r = p.fs;
- t->sz = Size(t->l) + Size(t->r) + 1;
- t->mn = min(min(Minn(t->l), Minn(t->r)), t->x);
- return {t, p.sc};
- }
- }
- Treap* Merge(Treap* L, Treap* R) {
- if (L == nullptr) {
- return R;
- }
- if (R == nullptr) {
- return L;
- }
- if (L->y > R->y) {
- L->r = Merge(L->r, R);
- L->sz = Size(L->l) + Size(L->r) + 1;
- L->mn = min(min(Minn(L->l), Minn(L->r)), L->x);
- return L;
- } else {
- R->l = Merge(L, R->l);
- R->sz = Size(R->l) + Size(R->r) + 1;
- R->mn = min(min(Minn(R->l), Minn(R->r)), R->x);
- return R;
- }
- }
- Treap* Insert(Treap *t, int x) {
- if (t == nullptr) {
- return new Treap(x);
- }
- int minn = min(Minn(t->l), t->x);
- if (minn < x) {
- Treap* p = Insert(t->l, x);
- t->l = nullptr;
- return Merge(p, t);
- } else {
- Treap* p = Insert(t->r, x);
- t->r = nullptr;
- return Merge(t, p);
- }
- }
- int d[max_n];
- void print(Treap* t) {
- if (t->l != nullptr) {
- print(t->l);
- }
- if (t->x) {
- cout << d[t->x] << ' ';
- }
- if (t->r != nullptr) {
- print(t->r);
- }
- }
- int main() {
- freopen("girls.in", "r", stdin);
- freopen("girls.out", "w", stdout);
- int n;
- cin >> n;
- int a[n], b[n];
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- d[a[i]] = i + 1;
- }
- Treap* T = new Treap(0);
- for (int i = 0; i < n; i++) {
- cin >> b[i];
- pair <Treap*, Treap*> p = Split(T, b[i] - 1);
- p.sc = Insert(p.sc, a[i]);
- T = Merge(p.fs, p.sc);
- }
- print(T);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement