Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.70 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define fs first
  4. #define sc second
  5.  
  6. using namespace std;
  7.  
  8. const int INF = 1e9 + 228;
  9. const int max_n = 1e5 + 228;
  10.  
  11. struct Treap {
  12. int x, y;
  13. int sz, mn;
  14. Treap *l, *r;
  15. Treap (int _x) {
  16. sz = x = mn = _x;
  17. y = rand();
  18. l = nullptr;
  19. r = nullptr;
  20. }
  21. };
  22.  
  23. int Size(Treap* t) {
  24. if (t == nullptr) {
  25. return 0;
  26. }
  27. return t->sz;
  28. }
  29.  
  30. int Minn(Treap* t) {
  31. if (t == nullptr) {
  32. return INF;
  33. }
  34. return t->mn;
  35. }
  36.  
  37. pair <Treap*, Treap*> Split(Treap* t, int k) {
  38. if (t == nullptr) {
  39. return {nullptr, nullptr};
  40. }
  41. if (k == 0) {
  42. return {nullptr, t};
  43. }
  44. int ls = Size(t->l);
  45. if (ls >= k) {
  46. pair <Treap*, Treap*> p = Split(t->l, k);
  47. t->l = p.sc;
  48. t->sz = Size(t->l) + Size(t->r) + 1;
  49. t->mn = min(min(Minn(t->l), Minn(t->r)), t->x);
  50. return {p.fs, t};
  51. } else {
  52. pair <Treap*, Treap*> p = Split(t->r, k - ls - 1);
  53. t->r = p.fs;
  54. t->sz = Size(t->l) + Size(t->r) + 1;
  55. t->mn = min(min(Minn(t->l), Minn(t->r)), t->x);
  56. return {t, p.sc};
  57. }
  58. }
  59.  
  60. Treap* Merge(Treap* L, Treap* R) {
  61. if (L == nullptr) {
  62. return R;
  63. }
  64. if (R == nullptr) {
  65. return L;
  66. }
  67. if (L->y > R->y) {
  68. L->r = Merge(L->r, R);
  69. L->sz = Size(L->l) + Size(L->r) + 1;
  70. L->mn = min(min(Minn(L->l), Minn(L->r)), L->x);
  71. return L;
  72. } else {
  73. R->l = Merge(L, R->l);
  74. R->sz = Size(R->l) + Size(R->r) + 1;
  75. R->mn = min(min(Minn(R->l), Minn(R->r)), R->x);
  76. return R;
  77. }
  78. }
  79.  
  80. Treap* Insert(Treap *t, int x) {
  81. if (t == nullptr) {
  82. return new Treap(x);
  83. }
  84. int minn = min(Minn(t->l), t->x);
  85. if (minn < x) {
  86. Treap* p = Insert(t->l, x);
  87. t->l = nullptr;
  88. return Merge(p, t);
  89. } else {
  90. Treap* p = Insert(t->r, x);
  91. t->r = nullptr;
  92. return Merge(t, p);
  93. }
  94. }
  95.  
  96. int d[max_n];
  97.  
  98. void print(Treap* t) {
  99. if (t->l != nullptr) {
  100. print(t->l);
  101. }
  102. if (t->x) {
  103. cout << d[t->x] << ' ';
  104. }
  105. if (t->r != nullptr) {
  106. print(t->r);
  107. }
  108. }
  109.  
  110. int main() {
  111. freopen("girls.in", "r", stdin);
  112. freopen("girls.out", "w", stdout);
  113. int n;
  114. cin >> n;
  115. int a[n], b[n];
  116. for (int i = 0; i < n; i++) {
  117. cin >> a[i];
  118. d[a[i]] = i + 1;
  119. }
  120. Treap* T = new Treap(0);
  121. for (int i = 0; i < n; i++) {
  122. cin >> b[i];
  123. pair <Treap*, Treap*> p = Split(T, b[i] - 1);
  124. p.sc = Insert(p.sc, a[i]);
  125. T = Merge(p.fs, p.sc);
  126. }
  127. print(T);
  128. return 0;
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement