fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector < pair<bool,long long int> > que;
  4. vector <long long int> sz;
  5. int main()
  6. {
  7. 	// freopen("input.txt", "r", stdin);
  8. 	ios_base::sync_with_stdio(0);
  9. 	int m;
  10. 	cin>>m;
  11. 	que.push_back(make_pair(false,1ll));
  12. 	sz.push_back(1ll);
  13. 	while(m--)
  14. 	{
  15. 		char ch;
  16. 		cin>>ch;
  17. 		if(ch == '+')
  18. 		{
  19. 			long long int k;
  20. 			cin>>k;
  21. 			if(k == 1)
  22. 			{
  23. 				if(que.back().first)
  24. 				{
  25. 					que.back().second++;
  26. 					sz.back()++;
  27. 				}
  28. 				else
  29. 				{
  30. 					que.push_back(make_pair(true,1ll));
  31. 					sz.push_back(1+sz.back());
  32. 				}
  33. 			}
  34. 			else
  35. 			{
  36. 				que.push_back(make_pair(false,k));
  37. 				sz.push_back(k*sz.back() + 1);
  38. 			}
  39. 		}
  40. 		else
  41. 		{
  42. 			long long int org_x,org_y,x,y;
  43. 			cin>>org_x>>org_y;
  44. 			x = org_x;
  45. 			y = org_y;
  46. 			long long int sep_depth = 0;
  47. 			bool found = false;
  48. 			for (int i = que.size()-1; i >= 0 && !found; --i)
  49. 			{
  50. 				if(que[i].first)
  51. 				{
  52. 					if(x > que[i].second && y > que[i].second)
  53. 					{
  54. 						x-=que[i].second;
  55. 						y-=que[i].second;
  56. 						sep_depth+=que[i].second;
  57. 					}
  58. 					else
  59. 					{
  60. 						sep_depth+=min(x,y);
  61. 						found = true;
  62. 					}
  63. 				}
  64. 				else
  65. 				{
  66. 					if(x > 1ll && y > 1ll)
  67. 					{
  68. 						x--;
  69. 						y--;
  70. 						sep_depth++;
  71. 						long long int v1 = (x-1ll)/sz[i-1];
  72. 						long long int v2 = (y-1ll)/sz[i-1];
  73. 						if(v1 == v2)
  74. 						{
  75. 							x = (x-1ll)%sz[i-1];
  76. 							y = (y-1ll)%sz[i-1];
  77. 							x++;
  78. 							y++;
  79. 						}
  80. 						else
  81. 						{
  82. 							found = true;
  83. 						}
  84. 					}
  85. 					else
  86. 					{
  87. 						sep_depth++;
  88. 						found = true;
  89. 					}
  90. 				}
  91. 			}
  92. 			// cout<<sep_depth<<"\n";
  93. 			x = org_x;
  94. 			long long int x_depth = 0;
  95. 			found = false;
  96. 			for (int i = que.size()-1; i >= 0 && !found; --i)
  97. 			{
  98. 				if(que[i].first)
  99. 				{
  100. 					if(x > que[i].second)
  101. 					{
  102. 						x-=que[i].second;
  103. 						x_depth+=que[i].second;
  104. 					}
  105. 					else
  106. 					{
  107. 						x_depth+=x;
  108. 						found = true;
  109. 					}
  110. 				}
  111. 				else
  112. 				{
  113. 					if(x > 1ll)
  114. 					{
  115. 						x--;
  116. 						x_depth++;
  117. 						x = (x-1ll)%sz[i-1];
  118. 						x++;
  119. 					}
  120. 					else
  121. 					{
  122. 						x_depth++;
  123. 						found = true;
  124. 					}
  125. 				}
  126. 			}
  127. 			// cout<<x_depth<<"\n";
  128. 			y = org_y;
  129. 			long long int y_depth = 0;
  130. 			found = false;
  131. 			for (int i = que.size()-1; i >= 0 && !found; --i)
  132. 			{
  133. 				// cout<<que[i].first<<" "<<que[i].second<<" "<<y<<"\n";
  134. 				if(que[i].first)
  135. 				{
  136. 					if(y > que[i].second)
  137. 					{
  138. 						y-=que[i].second;
  139. 						y_depth+=que[i].second;
  140. 					}
  141. 					else
  142. 					{
  143. 						y_depth+=y;
  144. 						found = true;
  145. 					}
  146. 				}
  147. 				else
  148. 				{
  149. 					if(y > 1ll)
  150. 					{
  151. 						y--;
  152. 						y_depth++;
  153. 						y = (y-1ll)%sz[i-1];
  154. 						y++;
  155. 					}
  156. 					else
  157. 					{
  158. 						y_depth++;
  159. 						found = true;
  160. 					}
  161. 				}
  162. 			}
  163. 			// cout<<y_depth<<"\n";
  164. 			assert(sep_depth <= x_depth && sep_depth <= y_depth);
  165. 			cout<<(x_depth-sep_depth)+(y_depth-sep_depth)<<"\n";
  166. 		}
  167. 	}
  168. 	return 0;
  169. }
Success #stdin #stdout 0s 3280KB
comments (?)
stdin
copy 
8
+ 1
? 1 2
+ 1
? 1 3
+ 2
? 2 5
? 7 4
? 6 6
stdout
copy 
1
2
2
6
0
https://ideone.com/YU265V
language:
C++ (gcc 8.3)
created:
9 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!