fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int solve(int n, vector<int> base, const string& s) {
  6.   for (int i = 0; i < s.size(); i++) {
  7.     for (int j = 0; j < n - 1 - i; j++) {
  8.       base[j] =
  9.           (s[i] == 'M') ? max(base[j], base[j + 1]) : min(base[j], base[j + 1]);
  10.     }
  11.   }
  12.   return base[0];
  13. }
  14.  
  15. vector<int> sad(const vector<int>& base, int len, bool is_max) {
  16.   deque<int> dq;
  17.   vector<int> res;
  18.   for (int i = 0; i < base.size(); i++) {
  19.     while (!dq.empty() && (is_max ? (base[dq.back()] <= base[i])
  20.                                   : (base[dq.back()] >= base[i]))) {
  21.       dq.pop_back();
  22.     }
  23.     dq.push_back(i);
  24.     if (dq.front() <= i - len) dq.pop_front();
  25.     if (i >= len - 1) res.push_back(base[dq.front()]);
  26.   }
  27.   return res;
  28. }
  29.  
  30. int sad_solve(int n, vector<int> base, string s) {
  31.   int i = 0;
  32.   while (i < s.size() && base.size() > 1) {
  33.     int j = i, len = 0;
  34.     while (j < s.size() && s[j] == s[i]) j++, len++;
  35.     len++;
  36.     if (base.size() < len) break;
  37.     base = sad(base, len, s[i] == 'M');
  38.     i = j;
  39.   }
  40.   return base[0];
  41. }
  42.  
  43. int main() {
  44.   int n;
  45.   cin >> n;
  46.   vector<int> base(n);
  47.   for (int& x : base) {
  48.     cin >> x;
  49.   }
  50.   string s;
  51.   cin >> s;
  52.   cout << solve(n, base, s) << endl;
  53.   cout << sad_solve(n, base, s);
  54.   return 0;
  55. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
7
3 1 4 5 6 2 1
MmmMmM
stdout
copy 
5
5
https://ideone.com/mSK0qO
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

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!