Submission #1326489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326489		vtnoo	Monochrome Points (JOI20_monochrome)	C++20	0 / 100	1 ms	1080 KiB

monochrome

#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()
#define sz(a) ((int) a.size())
#define pb push_back
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int INF=1e9;
int n,m;
int ans=0;
string s;
const int MAXN=2e5+5;
int fen[MAXN];
vector<int>b,w;
int que(int x){
	int v=0;
	for(;x;x-=x&-x)v+=fen[x];
	return v;
}
void upd(int x,int v){
	for(;x<MAXN;x+=x&-x)fen[x]+=v;
}
int get_sum(int a,int b){
	return que(b)-que(a);
}
int calc(vector<pair<int,int>>&p){
	memset(fen,0,sizeof(fen));
	int cur=0;
	int mm=sz(p)*2;
	vector<int>mpos(mm);
	L(i,0,n-1){
		mpos[p[i].fst]=i;
		mpos[p[i].snd]=i;
	}
	vector<int>lst(n,-1);
	L(i,0,mm-1){
		int j=mpos[i];
		if(lst[j]==-1){
			lst[j]=i;
			upd(i+1,1);
		}else{
			upd(lst[j]+1,-1);
			cur+=get_sum(lst[j]+1,i);
		}
	}
	return cur;
}
int check(int mm){
	vector<pair<int,int>>p;
	int j=0,cur=mm;
	int aa=b[j++],bb=w[cur];
	if(aa>bb)swap(aa,bb);
	p.pb({aa,bb});
	L(pasos,1,n-1){
		cur++;
		cur%=n;
		int aa_=b[j++],bb_=w[cur];
		if(aa_>bb_)swap(aa_,bb_);
		p.pb({aa_,bb_});
	}
	return calc(p);
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	cin>>n;
	cin>>s;
	m=n*2;
	L(i,0,m-1){
		if(s[i]=='B')b.pb(i);
		else w.pb(i);
	}
	sort(all(b));
	sort(all(w));
	int l=0,r=sz(w)+1;
	while(r-l>1){
		int mm=(r+l)/2;
		if(check(mm)<=check(mm-1)){
			l=mm;
		}else r=mm;
	}
	cout<<max({(l>0?check(l-1):0),check(l),check(r),(r<sz(w)-1?check(r+1):0)})<<endl;
}

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