Submission #1326385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326385		joacru	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	2095 ms	15308 KiB

monochrome

#include <iostream>
#include <algorithm>
#include <vector>

#define forn(i,n) for(int i=0;i<(int)n;++i)

#define DBG(a) cerr<<#a<<" = "<<a<<endl
#define DBGA(a) cerr<<#a<<" = "<<a<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, vector<T> &v){
	os<<"[";
	forn(i,SZ(v)){
		if(i) os<<", ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

typedef long long ll;

struct ST{
	int n;
	vector<int> st;
	void init(int _n){
		n = 1<<(32-__builtin_clz(_n-1));
		st.resize(2*n-1);
	}
	void update(int i, int x){
		i += n-1;
		st[i] += x;
		while(i){
			i = (i-1)/2;
			st[i] = st[2*i+1]+st[2*i+2];
		}
	}
	int query(int ql, int qr, int l, int r, int i){
		if(l>=qr||r<=ql) return 0;
		if(l>=ql&&r<=qr) return st[i];
		int m=(l+r)/2;
		return query(ql,qr,l,m,2*i+1)+query(ql,qr,m,r,2*i+2);
	}
	int query(int l, int r){
		return query(l,r,0,n,0);
	}
} mono;

ll check(int k, vector<int> a, vector<int> b){
	int n = SZ(a);
	rotate(b.begin(), b.begin()+k, b.end());
	vector<pair<int,int>> rs;
	forn(i,n){
		int l = a[i], r = b[i];
		if(l > r) swap(l, r);
		rs.push_back({l, r});
		rs.push_back({r, l});
	}
	sort(ALL(rs));
	ll ret = 0;
	for(auto x: rs){
		if(x.first < x.second){
			ret += mono.query(x.first, x.second);
			mono.update(x.second, +1);
		} else{
			mono.update(x.first, -1);
		}
	}
	return ret;
}

void solve(){
	int n;
	string s;
	cin>>n>>s;
	
	mono.init(2*n);
	vector<int> a, b;
	forn(i,2*n){
		if(s[i] == 'W') a.push_back(i);
		else b.push_back(i);
	}
	
	int l=0, r=n+1;
	while(l+1<r){
		int m = (l+r)/2;
		ll x = check(m-1, a, b), y = check(m, a, b);
		if(y > x){
			l = m;
		} else{
			r = m; // ???
		}
	}
	
	ll ans = check(l, a, b);
	cout<<ans<<"\n";
		
}

int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
	freopen("input.in", "r", stdin);
	int tcs;
	cin>>tcs;
	while(tcs--)
	#endif
	solve();
	
	return 0;
}

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