fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4. #define fo(i,n) for(i=0;i<n;i++)
  5. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  6. #define ll long long
  7. #define all(x) x.begin(), x.end()
  8. #define vi vector<int>
  9. //posu[3] = 5 means 3rd U 5th position pe
  10. //pred[4] = 7 means 4....n-1 tak 7 D hai
  11. //nowu[4] = 10 means 0 to 4 tak 10 U hai
  12. int n;
  13. int AT;
  14. vi posd[2], posu[2], pred[2], nowu[2], lastd[2], disd[2], disu[2];
  15. void build(string &s, vi &posd, vi &posu, vi &pred, vi &nowu, vi &lastd){
  16. int i, n = s.size();
  17. int cntd = 0, cntu = 0;
  18. pred[n] = 0;
  19. Fo(i, n-1, -1) pred[i] = pred[i+1]+(s[i]=='D');
  20. nowu[0] = s[0] == 'U';
  21. Fo(i, 1, n) nowu[i] = nowu[i-1]+(s[i]=='U');
  22. fo(i, n){
  23. if(s[i]=='U'){
  24. ++cntu;
  25. posu[cntu] = i;
  26. }
  27. }
  28. Fo(i, n-1, -1){
  29. if(s[i]=='D'){
  30. ++cntd;
  31. posd[cntd] = i;
  32. }
  33. }
  34. lastd[0] = -1;
  35. fo(i, n) {
  36. if(s[i]=='D'){
  37. lastd[i]=i, disd[AT][i] = i;
  38. }
  39. else if(i) lastd[i] = lastd[i-1];
  40. if(i) disd[AT][i] += disd[AT][i-1];
  41. }
  42. disu[AT][n] = 0;
  43. Fo(i, n-1, -1){
  44. if(s[i]=='U'){
  45. ++cntd;
  46. posd[cntd] = i;
  47. disu[AT][i] = n-i;
  48. }
  49. disu[AT][i] += disu[AT][i+1];
  50. }
  51. }
  52. ll f(int x, int y, int cnt){
  53. //x>y
  54. if(x<=y)return 0;
  55. cnt--;
  56. ll ans = disd[AT][x]-disd[AT][y]-cnt*y;
  57. return ans;
  58. }
  59. ll g(int x, int y, int cnt){
  60. //x>y
  61. if(x<=y)return 0;
  62. cnt--;
  63. ll ans = disu[AT][y]-disu[AT][x]-cnt*(n-x);
  64. return ans;
  65. }
  66. ll query(int x1, vi &posd, vi &posu, vi &pred, vi &nowu, vi &lastd){
  67. ll ans = 0;
  68. int x2 = lastd[x1];
  69. // cout<<x1<<" "<<x2<<endl;
  70. int x = nowu[x2], y = pred[x1];
  71. int r1 = posd[y], r2 = posd[1];
  72. int l1 = posu[x], l2 = posu[1];
  73. if (l2>x2) l2 = -1;
  74. if (l1>x2) l1 = -1;
  75. if(r2<x1) r2 = -1;
  76. if(r1<x1) r1 = -1;
  77. ll base1 = r1-x1, base2 = x2-l1;
  78. int nou = x1-x2-1;
  79. if(x2==-1)x = 0;
  80. int cut = max(0, nou);
  81. // cout<<nou<<" ."<<cut<<endl;
  82. // cout<<l2<<" "<<l1<<" "<<x2<<" "<<x1<<" "<<r1<<" "<<r2<<endl;
  83. // cout<<x<<" "<<y<<" "<<base1<<endl;
  84. if (nou >= y){
  85. ans = y + n-(x1-y) + 2*y*base1 + 2*f(r2,r1,y);
  86. return ans;
  87. }
  88. int r2_ = r1;
  89. if(cut){
  90. y -= cut;
  91. r2_ = posd[y+1];
  92. // cout<<base1<<" "<<y<<" "<<r2_<<" "<<r1<<endl;
  93. ans = 2*cut*(base1) +cut+ 2*f(r2_, r1, y);
  94. r2_ = posd[y];
  95. // cout<<r2_<<" "<<r1<<endl;
  96. base1 = r2_-x2-1;
  97. }
  98. // cout<<ans<<" "<<base1<<endl;
  99. // cout<<x<<" "<<y<<endl;
  100. if(x2==-1){
  101. return ans+1 + 2*(base1);
  102. }
  103. ll steps1 = x+1, steps2 = x;
  104. int l2_ = l2, r3 = posd[y-x];
  105. if (x<y){
  106. // cout<<base1<<" "<<base2<<endl;
  107. // cout<<x<<" "<<y<<endl;
  108. // cout<<r2_<<" "<<r3<<endl;
  109. ans += x2+1;
  110. ans += 2*steps1*(base1) + steps1 + 2*f(r3,r2_, x+1);
  111. ans += 2*steps2*(base2) + steps2 + 2*g(l1,l2_,x);
  112. return ans;
  113. }
  114. if (x==y){
  115. steps1 = steps2 = x; r3 = r2, l2_ = l2;
  116. // cout<<l2_<<" "<<l1<<" "<<r2_<<" "<<r3<<endl;
  117. ans += n-x2-1;
  118. // cout<<'s'<<" "<<x1<<endl;
  119. ans += 2*steps1*(base1) + steps1 + 2*f(r3,r2_,y);
  120. ans += 2*steps2*(base2) + steps2 + 2*g(l1,l2_,x);
  121. return ans;
  122. }
  123. if (x>y){
  124. steps1 = steps2 = y; r3 = r2, l2_ = posu[x-y+1];
  125. ans += n-x2-1;
  126. ans += 2*steps1*(base1) + steps1 + 2*f(r3,r2_, y);
  127. ans += 2*steps2*(base2) + steps2 + 2*g(l1,l2_,y);
  128. return ans;
  129. }
  130. }
  131. int main()
  132. {
  133. ios_base::sync_with_stdio(false);
  134. cin.tie(NULL);
  135. int i,k,j;
  136. string s;
  137. cin>>n;
  138. cin>>s;
  139. string ss = s;
  140. fo(i, n) ss[i] = s[i]=='U'?'D':'U';
  141. reverse(all(ss));
  142. // cout<<s<<" "<<ss<<endl;
  143. fo(i, 2){
  144. lastd[i].resize(n+2, -1);
  145. disd[i].resize(n+2, 0);
  146. disu[i].resize(n+2, 0);
  147. pred[i].resize(n+2, -1);
  148. nowu[i].resize(n+2, -1);
  149. posd[i].resize(n+2, -1);
  150. posu[i].resize(n+2, -1);
  151. }
  152. AT = 0;
  153. build(s,posd[0], posu[0], pred[0], nowu[0], lastd[0]);
  154. AT = 1;
  155. build(ss,posd[1], posu[1], pred[1], nowu[1], lastd[1]);
  156. // fo(i, n) cout<<disu[0][i]<<" ";
  157. // cout<<endl;
  158. // fo(i, n) cout<<pred[0][i]<<" ";
  159. // cout<<endl;
  160. int at = 0;
  161.  
  162. Fo(i, 0, n){
  163. at = (s[i]=='D') ;
  164. int ni = i;
  165. AT = at;
  166. if(at) ni = n-i-1;
  167. cout<<query(ni, posd[at], posu[at], pred[at], nowu[at], lastd[at])<<" ";
  168. }
  169. return 0;
  170. }
  171.  
Success #stdin #stdout 0s 3472KB
stdin
10
UUDUDUUDDU
stdout
5 12 23 34 36 27 18 11 6 1