ProgMe

Untitled

Feb 16th, 2021
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.87 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <bits/extc++.h>
  3. #include <tr2/dynamic_bitset>
  4.  
  5. #define int int64_t
  6.  
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9. using namespace __gnu_cxx;
  10.  
  11. template<typename T>
  12. using orset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
  13.  
  14. template<typename T>
  15. using ormultiset = tree<T, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
  16.  
  17. const int N = 100;
  18. int n;
  19. int t[4 * N];
  20. int a[N];
  21. int d[N];
  22.  
  23. void build (int v, int tl, int tr) {
  24. if (tl == tr)
  25. t[v] = tl;
  26. else {
  27. int tm = (tl + tr)>>1;
  28. build(v<<1, tl, tm);
  29. build(v<<1|1, tm+1, tr);
  30. if(a[t[v<<1]] >= a[t[v<<1|1]])
  31. t[v] = t[v<<1];
  32. else
  33. t[v] = t[v<<1|1];
  34. }
  35. }
  36.  
  37. int get(int v, int tl, int tr, int l, int r) {
  38. if (l > r)
  39. return -1;
  40. if (l == tl && r == tr)
  41. return t[v];
  42. int tm = (tl + tr) / 2;
  43. int l_ans = get(v<<1, tl, tm, l, min(r, tm)), r_ans = get(v<<1|1, tm + 1, tr, max(tm + 1, l), r);
  44. if(l_ans == -1)
  45. return r_ans;
  46. if(r_ans == -1)
  47. return l_ans;
  48. if(a[l_ans] >= a[r_ans])
  49. return l_ans;
  50. else
  51. return r_ans;
  52. }
  53.  
  54. void rec(int l, int r, int deep = 0){
  55. if (l > r)
  56. return;
  57. if(l == r){
  58. d[l] = deep;
  59. return;
  60. }
  61. int mx_ind = get(1, 0, n - 1, l, r);
  62. d[mx_ind] = deep;
  63. rec(l, mx_ind - 1, deep + 1);
  64. rec(mx_ind + 1, r, deep + 1);
  65. }
  66.  
  67. int32_t main()
  68. {
  69. ios::sync_with_stdio(false);
  70. int q;
  71. cin >> q;
  72. while(q--){
  73. cin >> n;
  74. for(int i = n; i < 2 * n; i++) {
  75. cin >> a[i - n];
  76. t[i] = i - n;
  77. }
  78. build(1, 0, n - 1);
  79. rec(0, n - 1);
  80. for(int i = 0; i < n; i++)
  81. cout << d[i] << ' ';
  82. cout << '\n';
  83. }
  84. }
  85.  
Advertisement
Add Comment
Please, Sign In to add comment