Submission #2195233

---

Source Code Expand

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

int n,a[100009],c[100009],e[300009],f[300009],len; string S;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > PQ1,PQ2;
bool record[500009];
set<int>LL,RR;

void query_1(){
	len++;
	while(!PQ1.empty()){
		pair<int,int>E=PQ1.top();
		if(f[E.second]!=E.first) {
			PQ1.pop();continue;
		}
		if(E.first>len) break;
		// 間の区間を消す
		PQ1.pop();f[E.second]=0;
		
		// 2 個の区間を消す、新たな区間を挿入
		auto itr1=RR.lower_bound(E.second);
		int GL=*itr1,GR=E.second+E.first;
		PQ2.push(make_pair(GL,GR-GL+e[GL]));
		e[GL]=(GR-GL+e[GL]);e[GR]=0;LL.erase(-GR);RR.erase(GR);
	}
}

void query_2(){
	len--;
	while(!PQ2.empty()){
		pair<int,int>E=PQ2.top();
		if(e[E.second]!=E.first){
			PQ2.pop();continue;
		}
		if(E.first>(-len)) break;
		//区間を消す
		PQ2.pop();e[E.second]=0;
		LL.erase(-E.second);RR.erase(E.second);
		
		//間の区間を結合させる
		auto itr1=RR.lower_bound(E.second);
		auto itr2=LL.lower_bound(E.second);
		int GL=*itr1,GR=*itr2;GR*=-1;
		PQ2.push(make_pair(GL,GR-GL-e[GL]));
		f[GL+e[GL]]=GR-GL-e[GL];
		f[E.second+E.first]=0;
	}
}

bool solve(int I){
	for(int i=0;i<n;i++){e[i]=0;f[i]=0;record[i]=false;}
	LL.clear();RR.clear();len=0;
	while(!PQ1.empty()) PQ1.pop();
	while(!PQ2.empty()) PQ2.pop();
	for(int i=0;i<n;i++){
		if(a[i]>=I) c[i]=1;
		else c[i]=0;
	}
	int s=0;
	for(int i=0;i<=n;i++){
		if(c[i]==1) s++;
		else{
			if(s>=1) PQ2.push(make_pair(s,i-s));
			LL.insert(-(i-s));RR.insert((i-s));e[i-s]=s;
			s=0;
		}
	}
	s=-1000000;
	for(int i=0;i<n;i++){
		if(c[i]==0) s++;
		else{
			if(s>=1) PQ1.push(make_pair(s,i-s));
			if(s>=1)f[i-s]=s;
			s=0;
		}
	}
	//cout<<endl<<I<<": ";for(int i=0;i<n;i++) cout<<c[i]<<" ";cout<<endl;
	int sum=0;
	for(int i=0;i<S.size();i++){
		//for(int j=0;j<n;j++) cout<<e[j]<<" ";cout<<endl;
		if(S[i]=='M') query_1();
		if(S[i]=='m') query_2();
		if(S[i]=='M') sum++;
	}
	while(!PQ2.empty()){
		pair<int,int>E=PQ2.top();PQ2.pop();
		if(e[E.second]!=E.first) continue;
		for(int i=0;i<E.first+len;i++) record[E.second+i]=true;
	}
	return record[sum];
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	cin>>S;
	int L=0,R=(1<<17),M,maxn;
	for(int i=0;i<20;i++){
		M=(L+R)/2;
		bool p1=solve(M);
		if(p1==true){maxn=max(maxn,M);L=M;}
		else{R=M;}
	}
	cout<<maxn<<endl;
	return 0;
}

Submission Info

Judge Result