Submission #1190186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190186		drakozs	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	677 ms	5596 KiB

monochrome

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define pb push_back

using namespace std;

const int MAXN = 200000 + 5;
static int w[MAXN], b[MAXN];
static pair<int,int> allPair[MAXN];
int BIT[2*MAXN + 5];

void bit_update(int pos, int M) {
    for (pos += 1; pos <= M; pos += pos & -pos)
        BIT[pos]++;
}

ll bit_sum(int pos) {
    ll s = 0;
    for (pos += 1; pos > 0; pos -= pos & -pos)
        s += BIT[pos];
    return s;
}

ll bit_range(int l, int r) {
    return (l > r ? 0LL : bit_sum(r) - (l ? bit_sum(l-1) : 0LL));
}

ll getAns(int n, int k){
	int M = 2 * n;
	memset(BIT, 0, sizeof(int)*(M+2));
	ll curr = 0;
	for (int i = 0; i < n; i++){
		int wPos = w[i], bPos = b[(i + k) % n];
		allPair[i] = {min(wPos, bPos), max(wPos, bPos)};
	}
	sort(allPair, allPair + n);
	for (int i = 0; i < n; i++){
		curr += bit_range(allPair[i].first, allPair[i].second);
        bit_update(allPair[i].second, M);
	}
	return curr;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin >> n;
	string s;
	cin >> s;
	int curW = 0, curB = 0;
	for (int i = 0; i < 2 * n; i++){
		if (s[i] == 'W'){
			w[curW++] = i;
		}
		else{
			b[curB++] = i;
		}
	}
	ll ans = 0;
	int left = 0, right = n - 1, mid;
	while(left <= right){
		mid = (right - left) / 2 + left;
		ll curr = getAns(n, mid);
		ll prev = 0;
		if (mid - 1 >= 0){
			prev = getAns(n, mid - 1);
		}
		
		ans = max(ans, curr);
		if (curr > prev){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}
	}
	ans = max(ans, getAns(n, 0));
	ans = max(ans, getAns(n, n - 1));
	cout << ans << "\n";
	
	
	return 0;
}

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