fork download
copy 
  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
comments (?)
stdin
copy 
10
UUDUDUUDDU
stdout
copy 
5 12 23 34 36 27 18 11 6 1
https://ideone.com/8SaVmw
my template :)
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!