Submission #997883

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int MX = 100011;
const int LG = 19;
const int INF = 10000000;

struct RMaxQ //Warning : Change query return value manually if needed. INF is the dummy val
{
	int st[LG][MX];
	int initial[MX];
	
	int combine(int a, int b) //warning : change if neccesary
	{
		return max(a,b);
	}
	
	RMaxQ()
	{
		for(int i = 0; i < MX; i++) initial[i] = 0;
	}
	
	void init()
	{
		for(ll j = 0; j < LG; j++)
		{
			for(ll i = 0; i < MX; i++)
			{
				st[j][i] = INF;
				if(i + (1<<j) - 1 < MX)
				{
					if(j == 0) st[j][i] = initial[i];
					else st[j][i] = combine(st[j-1][i], st[j-1][i + (1<<(j-1))]);
				}
			}
		}
	}
	
	int query(int l, int r)
	{
		int k = 31 - __builtin_clz(r-l);
		return combine(st[k][l], st[k][r - (1<<k) + 1]);
	}
};

struct RMinQ //Warning : Change query return value manually if needed. INF is the dummy val
{
	int st[LG][MX];
	int initial[MX];
	
	int combine(int a, int b) //warning : change if neccesary
	{
		return min(a,b);
	}
	
	RMinQ()
	{
		for(int i = 0; i < MX; i++) initial[i] = INF;
	}
	
	void init()
	{
		for(ll j = 0; j < LG; j++)
		{
			for(ll i = 0; i < MX; i++)
			{
				st[j][i] = INF;
				if(i + (1<<j) - 1 < MX)
				{
					if(j == 0) st[j][i] = initial[i];
					else st[j][i] = combine(st[j-1][i], st[j-1][i + (1<<(j-1))]);
				}
			}
		}
	}
	
	int query(int l, int r)
	{
		int k = 31 - __builtin_clz(r-l);
		return combine(st[k][l], st[k][r - (1<<k) + 1]);
	}
};

RMaxQ M;
RMinQ m;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i = 0; i < n; i++)
	{
		cin>>M.initial[i];
	}
	string s;
	cin>>s;
	int t = -1;
	for(int i = 0; i < n - 1; i++)
	{
		if(s[i]=='M') t = i;
	}
	t++;
	M.init();
	for(int i = 0; i < n - t; i++)
	{
		m.initial[i] = M.query(i, i+t);
	}
	m.init();
	cout<<m.query(0,n-1)<<'\n';
}

Submission Info

Judge Result