Advertisement
Guest User

Untitled

a guest
Jan 29th, 2021
544
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.80 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = int(1e9);
  6.  
  7. struct segTree
  8. {
  9. int n;
  10. bool mx;
  11. vector<int> t;
  12.  
  13. void fix(int v)
  14. {
  15. t[v] = (mx ? max(t[v * 2 + 1], t[v * 2 + 2]) : min(t[v * 2 + 1], t[v * 2 + 2]));
  16. }
  17.  
  18. void build(int v, int l, int r)
  19. {
  20. if(l == r - 1)
  21. t[v] = (mx ? -INF : INF);
  22. else
  23. {
  24. int m = (l + r) / 2;
  25. build(v * 2 + 1, l, m);
  26. build(v * 2 + 2, m, r);
  27. fix(v);
  28. }
  29. }
  30.  
  31. void upd(int v, int l, int r, int pos, int val)
  32. {
  33. if(l == r - 1)
  34. t[v] = (mx ? max(t[v], val) : min(t[v], val));
  35. else
  36. {
  37. int m = (l + r) / 2;
  38. if(pos < m)
  39. upd(v * 2 + 1, l, m, pos, val);
  40. else
  41. upd(v * 2 + 2, m, r, pos, val);
  42. fix(v);
  43. }
  44. }
  45.  
  46. int get(int v, int l, int r, int L, int R)
  47. {
  48. if(L >= R)
  49. return (mx ? -INF : INF);
  50. if(l == L && r == R)
  51. return t[v];
  52. int m = (l + r) / 2;
  53. int lf = get(v * 2 + 1, l, m, L, min(R, m));
  54. int rg = get(v * 2 + 2, m, r, max(m, L), R);
  55. return (mx ? max(lf, rg) : min(lf, rg));
  56. }
  57.  
  58. void upd(int pos, int val)
  59. {
  60. upd(0, 0, n, pos, val);
  61. }
  62.  
  63. int get(int L, int R)
  64. {
  65. return get(0, 0, n, L, R);
  66. }
  67.  
  68. void build()
  69. {
  70. return build(0, 0, n);
  71. }
  72.  
  73. segTree() {};
  74. segTree(int n, bool mx) : n(n), mx(mx)
  75. {
  76. t.resize(4 * n);
  77. }
  78. };
  79.  
  80. int main()
  81. {
  82. int t;
  83. scanf("%d", &t);
  84. for(int _ = 0; _ < t; _++)
  85. {
  86. int n;
  87. scanf("%d", &n);
  88. vector<int> p(n);
  89. for(int i = 0; i < n; i++)
  90. scanf("%d", &p[i]);
  91. vector<int> dp(n + 1, -INF);
  92. vector<int> par(n + 1, -2);
  93. dp[0] = 0;
  94. par[0] = -1;
  95. vector<int> lf(n), rg(n);
  96. for(int i = 0; i < n; i++)
  97. {
  98. lf[i] = max(1, i - p[i] + 1);
  99. rg[i] = min(n, i + p[i] + 1);
  100. }
  101. segTree sn(n + 1, false);
  102. segTree sx(n, true);
  103. sn.build();
  104. sx.build();
  105. for(int i = 0; i < n; i++)
  106. sx.upd(i, rg[i]);
  107. sn.upd(0, 0);
  108. for(int i = 1; i <= n; i++)
  109. {
  110. int j = i - 1;
  111. int k = lf[j] - 1;
  112.  
  113. int m = sn.get(k, n + 1);
  114. if(m != INF)
  115. {
  116. int nval = max(sx.get(m, i - 1), i - 1);
  117. if(nval > dp[i])
  118. {
  119. dp[i] = nval;
  120. par[i] = m;
  121. }
  122. }
  123. if(dp[j] >= i && max(dp[j], rg[j]) > dp[i])
  124. {
  125. dp[i] = max(dp[j], rg[j]);
  126. par[i] = -1;
  127. }
  128. if(dp[j] > dp[i])
  129. {
  130. dp[i] = dp[j];
  131. par[i] = -1;
  132. }
  133. sn.upd(dp[i], i);
  134. }
  135. if(dp[n] != n)
  136. puts("NO");
  137. else
  138. {
  139. puts("YES");
  140. string ans;
  141. int cur = n;
  142. while(cur != 0)
  143. {
  144. if(par[cur] == -1)
  145. {
  146. cur--;
  147. ans += "R";
  148. }
  149. else
  150. {
  151. int pcur = par[cur];
  152. int diff = cur - pcur;
  153. ans += "L";
  154. for(int j = 0; j < diff - 1; j++)
  155. ans += "R";
  156. cur = pcur;
  157. }
  158. }
  159. reverse(ans.begin(), ans.end());
  160. puts(ans.c_str());
  161. }
  162. }
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement