Submission #2195009

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int n,a[100009],r,minx=(1<<30);string S;
priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>>Q;

int solve_1(){
	for(int i=0;i<=r;i++) Q.push(make_pair(a[i],i));
	minx=min(minx,Q.top().first);
	for(int i=r+1;i<n;i++){
		while(!Q.empty()){
			if(Q.top().second<i-r) Q.pop();
			else break;
		}
		Q.push(make_pair(a[i],i));
		minx=min(minx,Q.top().first);
	}
	return minx;
}

int t[100009],s[100009];

bool solve_bin(int I){
	for(int i=0;i<n;i++){
		if(a[i]>=I) t[i]=1;else t[i]=0;
	}
	for(int i=0;i<n-1;i++) s[i]=max(t[i],t[i+1]);
	if(n%2==0){
		int G=n/2-1;
		return min((bool)(s[G]),(bool)(s[G+1]));
	}
	else{
		int G=n/2;
		return (bool)(s[G]);
	}
}

int solve_2(){
	int L=0,R=1000000007,M,maxn=0;
	for(int i=0;i<36;i++){
		M=(L+R)/2;
		bool p1=solve_bin(M);
		if(p1==true) {maxn=max(maxn,M);L=M;}
		else{R=M;}
	}
	return maxn;
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	cin>>S;
	for(int i=0;i<S.size();i++){
		if(S[i]=='m') {r=i;break;}
	}
	bool flag=false;
	for(int i=r;i<S.size();i++){
		if(S[i]=='M') flag=true;
	}
	if(flag==false) cout<<solve_1()<<endl;
	else cout<<solve_2()<<endl;
	return 0;
}

Submission Info

Judge Result