Submission #998020

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const int M = 100100;

int n, a[M];
int b[M];
string s;
int sum[M];
int c[M];

void read() {
  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  cin >> s;
}

void build(int x) {
  for (int i = 0; i < n; ++i)
    b[i] = a[i] <= x;
}

int val() {
  int k = 0;
  while (k < n - 1 && s[k] == 'M')
    ++k;
  for (int i = 0; i < n; ++i)
    sum[i + 1] = sum[i] + b[i];

  ++k;
  for (int i = 0; i + k <= n; ++i)
    c[i] = (sum[i + k] - sum[i]) > 0;
  
  int ans = 1;
  for (int i = 0; i + k <= n; ++k)
    ans &= c[i];

  return ans;
}

void bin() {
  int l = 0, r = n;
  while (l < r) {
    int m = (l + r) / 2;
    build(m);
    if (val())
      r = m;
    else
      l = m + 1;
  }
  cout << l << endl;
}

int main() {
#ifdef LOCAL
  assert(freopen("b.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  read();
  bin();
}

Submission Info

Judge Result