Submission #1158693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158693		alexander707070	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	913 ms	6704 KiB

monochrome

#include<bits/stdc++.h>
#define MAXN 400007
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;
}

long long check(int pref){

	pairs.clear();

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

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

	for(int i=pref;i<n;i++){
		if(B[i] < W[i-pref]){
			return -2;
		}

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

	return solve();
}

int bin(){
	int l=0,r=n,tt;

	while(l+1<r){
		tt=(l+r)/2;
		long long curr=check(tt);

		if(curr==-1){
			r=tt;
		}else if(curr==-2){
			l=tt;
		}else{
			long long p=check(tt+1);
			
			if(curr<p){
				l=tt+1;
			}else{
				r=tt;
			}
		}
	}

	for(int s=-3;s<=3;s++){
		if(l+s>=0 and l+s<=n)ans=max(ans,check(l+s));
	}

	return ans;
}

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);
	}

	cout<<bin()<<"\n";

	return 0;
}

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