Submission #543307

#	Time	Username	Problem	Language	Result	Execution time	Memory
543307		8e7	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	823 ms	7520 KiB

monochrome

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn], p[maxn];
int bp[maxn], wp[maxn];
struct BIT{
	int bit[maxn];
	void init(int n) {
		for (int i = 0;i <= n + 1;i++) bit[i] = 0;
	}
	void modify(int ind, int val) {
		ind++;
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;	
	}
	int query(int ind) {
		ind++;
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} bit;
int main() {
	io
	int n;
	cin >> n;
	n *= 2;
	string s;
	cin >> s;
	int mi = 0, mpos = 0, cur = 0;
	for (int i = 0;i < n;i++) {
		if (cur < mi) {
			mi = cur;
			mpos = i;
		} 
		cur += (s[i] == 'B' ? 1 : -1);
	}
	int bi = 0, wi = 0;
	for (int i = 0;i < n;i++) {
		a[i] = (s[(mpos + i) % n] == 'B' ? 1 : -1);
		if (a[i] == 1) bp[bi++] = i;
		else wp[wi++] = i;
	}	
	auto getval = [&](int x) {
		for (int i = 0;i < n/2;i++) {
			p[bp[i]] = (i < x ? 1 : -1);
			p[wp[i]] = (i < n/2 - x ? 1 : -1);
		}
		int cur = 0;
		bit.init(n);
		ll ret = 0;
		int bi = 0, wi = 0;	
		//debug(x);
		//pary(p, p + n);
		for (int i = 0;i < n;i++) {
			cur += p[i];
			if (cur < 0) return 0LL;	
			if (p[i] == 1) {
				bit.modify(i, 1);
			} else {
				int cor = (a[i] > 0 ? wp[wi++] : bp[bi++]);
				//debug(i, cor);
				ret += bit.query(i) - bit.query(cor);	
				bit.modify(cor, -1);
			}
		}
		//debug(ret);
		return ret;
	};
	ll ans = 0;
	int lef = 0, rig = n / 2 + 1;
	while (lef < rig - 2) {
		int m1 = (2*lef + rig) / 3, m2 = (lef + 2 * rig) / 3;
		if (getval(m1) > getval(m2)) rig = m2;
		else lef = m1;
	}
	ans = max(ans, max(getval(lef), getval(lef + 1)));
	cout << ans << endl;
}

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