Submission #1158689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158689		alexander707070	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	2092 ms	6252 KiB

monochrome

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

int n,br[MAXN],pref[MAXN];
char c[MAXN];
vector<int> B,W;
vector< pair<int,int> > pairs;

long long ans;

struct Fenwick{
	int fen[MAXN];

	void update(int x,int val){
		while(x<=2*n){
			fen[x]+=val;
			x+=(x & (-x));
		}
	}

	int getsum(int x){
		int res=0;
		while(x>=1){
			res+=fen[x];
			x^=(x & (-x));
		}

		return res;
	}

	int sum(int l,int r){
		return getsum(r) - getsum(l-1);
	}
}fenwick;

long long solve(){
	
	long long res=0;
	sort(pairs.begin(),pairs.end());

	for(int i=1;i<=2*n;i++)pref[i]=0;

	for(auto s:pairs){
		fenwick.update(s.second,1);
		pref[s.second]=1;
	}

	for(int i=1;i<=2*n;i++)pref[i]+=pref[i-1];

	for(auto s:pairs){
		int k=fenwick.sum(s.first+1,s.second-1);

		res+=(s.second-s.first-1) - (pref[s.second-1]-pref[s.first]) - k;

		fenwick.update(s.second,-1);
	}

	return res;
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n;
	for(int i=1;i<=2*n;i++){
		cin>>c[i];
		if(c[i]=='B')B.push_back(i);
		else W.push_back(i);
	}

	for(int pref=0;pref<=n;pref++){
		bool ok=true;
		pairs.clear();

		for(int i=0;i<pref;i++){
			if(B[i] > W[n-pref+i]){
				ok=false; break;
			}

			pairs.push_back({B[i],W[n-pref+i]});
		}

		for(int i=pref;i<n;i++){
			if(B[i] < W[i-pref]){
				ok=false; break;
			}

			pairs.push_back({W[i-pref],B[i]});
		}

		if(!ok)continue;

		ans=max(ans,solve());
	}

	cout<<ans<<"\n";

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 0 / 65