Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2020
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6.  
  7.  
  8. struct minqueue {
  9. int f(int a, int b) {
  10. return min(a, b);
  11. }
  12.  
  13. stack<pair<int, int>> s1, s2;
  14.  
  15. void clear() {
  16. while (!s1.empty()) s1.pop();
  17. while (!s2.empty()) s2.pop();
  18. }
  19. void upd () {
  20. s2.push({s1.top().first, s1.top().first});
  21. s1.pop();
  22. while (!s1.empty()) {
  23. int x = s1.top().first;
  24. s1.pop();
  25. s2.push({x, f(x, s2.top().second)});
  26. }
  27. }
  28. void add (int x) {
  29. if (s1.empty()) s1.push({x, x});
  30. else s1.push({x, f(x, s1.top().second)});
  31. }
  32. void remove () {
  33. if (s2.empty()){
  34. upd();
  35. }
  36. s2.pop();
  37. }
  38. int get() {
  39. if (s1.empty()) {
  40. return s2.top().second;
  41. }
  42. if (s2.empty()) {
  43. return s1.top().second;
  44. }
  45. return f (s1.top().second, s2.top().second);
  46. }
  47. };
  48. struct maxqueue {
  49. int f(int a, int b) {
  50. return max(a, b);
  51. }
  52. stack<pair<int, int>> s1, s2;
  53.  
  54.  
  55. void clear() {
  56. while (!s1.empty()) s1.pop();
  57. while (!s2.empty()) s2.pop();
  58. }
  59. void upd () {
  60. s2.push({s1.top().first, s1.top().first});
  61. s1.pop();
  62. while (!s1.empty()) {
  63. int x = s1.top().first;
  64. s1.pop();
  65. s2.push({x, f(x, s2.top().second)});
  66. }
  67. }
  68. void add (int x) {
  69. if (s1.empty()) s1.push({x, x});
  70. else s1.push({x, f(x, s1.top().second)});
  71. }
  72. void remove () {
  73. if (s2.empty()){
  74. upd();
  75. }
  76. s2.pop();
  77. }
  78. int get() {
  79. if (s1.empty()) {
  80. return s2.top().second;
  81. }
  82. if (s2.empty()) {
  83. return s1.top().second;
  84. }
  85. return f (s1.top().second, s2.top().second);
  86. }
  87. };
  88.  
  89. void solve() {
  90. int n;
  91. cin >> n;
  92. vector<int> a(n);
  93. string s;
  94. for (int i = 0 ; i < n; ++ i) {
  95. cin >> a[i];
  96. }
  97. cin >> s;
  98. int lt = -1e9, rt = 1e9; //t - Tmin
  99. int lT = -1e9, rT = 1e9; //T - Tmax
  100. minqueue mnq;
  101. maxqueue mxq;
  102.  
  103. for (int i = 0; i < 4; ++ i) {
  104. mxq.add(a[i]);
  105. }
  106. bool f = true; // true - min, false - max
  107. for (int i = 4; i < n; ++ i) {
  108. if (f) {
  109. mxq.add(a[i]);
  110. if (s[i] == '0') {
  111. rt = min (rt, mxq.get());
  112. } else {
  113. lt = max(lt, mxq.get() + 1);
  114. f = false;
  115. int j = i;
  116. while (j - i < 4){
  117. mnq.add(a[j]);
  118. j++;
  119. }
  120. i = j - 1;
  121. mxq.clear();
  122. continue;
  123. }
  124. mxq.remove();
  125. }
  126. else {
  127. mnq.add(a[i]);
  128. if (s[i] == '1') {
  129. lT = max(lT, mnq.get());
  130. }
  131. else {
  132. rT = min(rT, mnq.get() - 1);
  133. f = true;
  134. int j = i;
  135. while (j - i < 4){
  136. mxq.add(a[j]);
  137. j++;
  138. }
  139. i = j;
  140. mnq.clear();
  141. continue;
  142. }
  143. mnq.remove();
  144. }
  145. }
  146. int l = max(lT, lt), r = min (rT, rt);
  147. if (l > r) {
  148. cout << lt << '!' << rt << "!!";
  149. cout << lT << '!' << rT << "!!";
  150. return;
  151. }
  152. cout << l << ' ' <<l;
  153.  
  154. }
  155.  
  156. signed main() {
  157. //freopen(".in", "r" , stdin);
  158. //freopen(".out", "w" , stdout);
  159. ios_base::sync_with_stdio(0);
  160. cin.tie(0);
  161. cout.tie(0);
  162. solve();
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement