Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- struct minqueue {
- int f(int a, int b) {
- return min(a, b);
- }
- stack<pair<int, int>> s1, s2;
- void clear() {
- while (!s1.empty()) s1.pop();
- while (!s2.empty()) s2.pop();
- }
- void upd () {
- s2.push({s1.top().first, s1.top().first});
- s1.pop();
- while (!s1.empty()) {
- int x = s1.top().first;
- s1.pop();
- s2.push({x, f(x, s2.top().second)});
- }
- }
- void add (int x) {
- if (s1.empty()) s1.push({x, x});
- else s1.push({x, f(x, s1.top().second)});
- }
- void remove () {
- if (s2.empty()){
- upd();
- }
- s2.pop();
- }
- int get() {
- if (s1.empty()) {
- return s2.top().second;
- }
- if (s2.empty()) {
- return s1.top().second;
- }
- return f (s1.top().second, s2.top().second);
- }
- };
- struct maxqueue {
- int f(int a, int b) {
- return max(a, b);
- }
- stack<pair<int, int>> s1, s2;
- void clear() {
- while (!s1.empty()) s1.pop();
- while (!s2.empty()) s2.pop();
- }
- void upd () {
- s2.push({s1.top().first, s1.top().first});
- s1.pop();
- while (!s1.empty()) {
- int x = s1.top().first;
- s1.pop();
- s2.push({x, f(x, s2.top().second)});
- }
- }
- void add (int x) {
- if (s1.empty()) s1.push({x, x});
- else s1.push({x, f(x, s1.top().second)});
- }
- void remove () {
- if (s2.empty()){
- upd();
- }
- s2.pop();
- }
- int get() {
- if (s1.empty()) {
- return s2.top().second;
- }
- if (s2.empty()) {
- return s1.top().second;
- }
- return f (s1.top().second, s2.top().second);
- }
- };
- void solve() {
- int n;
- cin >> n;
- vector<int> a(n);
- string s;
- for (int i = 0 ; i < n; ++ i) {
- cin >> a[i];
- }
- cin >> s;
- int lt = -1e9, rt = 1e9; //t - Tmin
- int lT = -1e9, rT = 1e9; //T - Tmax
- minqueue mnq;
- maxqueue mxq;
- for (int i = 0; i < 4; ++ i) {
- mxq.add(a[i]);
- }
- bool f = true; // true - min, false - max
- for (int i = 4; i < n; ++ i) {
- if (f) {
- mxq.add(a[i]);
- if (s[i] == '0') {
- rt = min (rt, mxq.get());
- } else {
- lt = max(lt, mxq.get() + 1);
- f = false;
- int j = i;
- while (j - i < 4){
- mnq.add(a[j]);
- j++;
- }
- i = j - 1;
- mxq.clear();
- continue;
- }
- mxq.remove();
- }
- else {
- mnq.add(a[i]);
- if (s[i] == '1') {
- lT = max(lT, mnq.get());
- }
- else {
- rT = min(rT, mnq.get() - 1);
- f = true;
- int j = i;
- while (j - i < 4){
- mxq.add(a[j]);
- j++;
- }
- i = j;
- mnq.clear();
- continue;
- }
- mnq.remove();
- }
- }
- int l = max(lT, lt), r = min (rT, rt);
- if (l > r) {
- cout << lt << '!' << rt << "!!";
- cout << lT << '!' << rT << "!!";
- return;
- }
- cout << l << ' ' <<l;
- }
- signed main() {
- //freopen(".in", "r" , stdin);
- //freopen(".out", "w" , stdout);
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement