fork download
  1. #include<bits/stdc++.h>
  2. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  3. #define ll long long
  4. using namespace std;
  5. #define left(i) (2*i + 1)
  6. #define right(i) (2*i + 2)
  7. #define parent(i) ((i-1)/2)
  8. #include <vector>
  9.  
  10. template<class T>
  11. class SegmentTree
  12. {
  13. public:
  14. SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
  15. SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
  16. T query(int l, int r);
  17. void update(int idx, T val);
  18. //TODO lazy propagation
  19. private:
  20. T *tree;
  21. void buildTree(std::vector<T> data);
  22. int segTreeSize;
  23. T valueForExtraNodes;
  24. T (*combine)(T obj1, T obj2);
  25. int calculateSize(int n);
  26. T queryHelper(int l,int r, int st, int ed, int node);
  27. };
  28.  
  29. template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
  30. T value, T (*combine)(T obj1, T obj2))
  31. {
  32. this->combine = combine;
  33. valueForExtraNodes = value;
  34. segTreeSize = calculateSize(data.size());
  35. buildTree(data);
  36. }
  37.  
  38. template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
  39. T value, T (*combine)(T obj1, T obj2))
  40. {
  41. this->combine = combine;
  42. valueForExtraNodes = value;
  43. segTreeSize = calculateSize(n);
  44.  
  45. std::vector<T> data;
  46. for(int i = 0; i < n; i++)
  47. data.push_back(ar[i]);
  48.  
  49. buildTree(data);
  50. }
  51.  
  52.  
  53. template<class T> int SegmentTree<T>::calculateSize(int n)
  54. {
  55. int pow2 = 1;
  56. while( pow2 < n)
  57. {
  58. pow2 = pow2 << 1;
  59. }
  60. return 2*pow2 - 1;
  61. }
  62.  
  63. template<class T> T SegmentTree<T>::query(int l, int r)
  64. {
  65. int st = 0, ed = segTreeSize/2;
  66. return queryHelper(l, r, st, ed, 0);
  67. }
  68.  
  69. template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
  70. {
  71. if( (r < st) || (l > ed) || (l > r) )
  72. return valueForExtraNodes;
  73. if(st >= l && ed <= r)
  74. return tree[node];
  75. T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
  76. T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
  77. return combine(leftVal, rightVal);
  78. }
  79.  
  80. template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
  81. {
  82. int n = data.size();
  83. tree = new T[segTreeSize];
  84. int extraNodes = (segTreeSize/2 + 1) - n;
  85. for(int i = segTreeSize - 1; i >= 0; i--)
  86. {
  87. if(extraNodes>0)
  88. {
  89. tree[i] = valueForExtraNodes;
  90. extraNodes--;
  91. }
  92. else if(n>0)
  93. {
  94. tree[i] = data[n-1];
  95. n--;
  96. }
  97. else
  98. tree[i] = combine(tree[left(i)], tree[right(i)]);
  99. }
  100. }
  101.  
  102. template<class T> void SegmentTree<T>::update(int idx, T val)
  103. {
  104. int segTreeIdx = (segTreeSize/2) + idx;
  105. tree[segTreeIdx] = val;
  106. while(parent(segTreeIdx) >= 0)
  107. {
  108. segTreeIdx = parent(segTreeIdx);
  109. if(right(segTreeIdx) < segTreeSize)
  110. tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
  111. if(segTreeIdx == 0)
  112. break;
  113. }
  114. }
  115.  
  116. int sum(int x,int y) { return x+y; }
  117. int main()
  118. {
  119. fast_io;
  120. int n;
  121. cin>>n;
  122.  
  123. vector<int> v(n);
  124. vector<int> present(n,1);
  125.  
  126. for(int i=0;i<n;i++)
  127. cin >> v[i];
  128.  
  129. SegmentTree<int> rangeSumQueries(present, 0, sum);
  130. for(int i = 0; i < n; i++)
  131. {
  132. int x;
  133. cin >> x;
  134. int lo = 0, hi = n - 1;
  135. while(lo!=hi)
  136. {
  137. int mid = (lo+hi)/2;
  138. int till_mid = rangeSumQueries.query(0,mid);
  139. if(till_mid > x)
  140. hi = mid - 1;
  141. else if(till_mid < x)
  142. lo = mid + 1;
  143. else
  144. {
  145. if(present[mid]){
  146. lo = mid;
  147. break;
  148. }
  149. else hi = mid - 1;
  150. }
  151. }
  152. present[lo] = 0;
  153. rangeSumQueries.update(lo, 0);
  154. cout << v[lo] <<' ';
  155. }
  156. return 0;
  157. }
  158.  
  159.  
Success #stdin #stdout 0s 4400KB
stdin
5
2 6 1 4 2
3 1 3 1 1
stdout
1 2 2 6 4