Submission #1190178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190178		drakozs	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2097 ms	10200 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
#define MAXN 200000

using namespace std;

int w[MAXN], b[MAXN];
pair<int, int> allPair[MAXN];
int segTree[8 * MAXN];

void update(int curr, int pos, int l, int r){
	segTree[curr]++;
	if (l == r) return;
	int mid = (r - l) / 2 + l;
	if (pos <= mid){
		update(curr * 2 + 1, pos, l, mid);
	}
	else{
		update(curr * 2 + 2, pos, mid + 1, r);
	}
}

ll getCount(int curr, int l, int r, int findL, int findR){
	if (l >= findL && r <= findR) return segTree[curr];
	int mid = (r - l) / 2 + l;
	ll ans = 0;
	if (findL <= mid){
		ans += getCount(curr * 2 + 1, l, mid, findL, findR);
	}
	if (findR > mid){
		ans += getCount(curr * 2 + 2, mid + 1, r, findL, findR);
	}
	return ans;
}

ll getAns(int n, int k){
	for (int i = 0; i < 8 * n; i++){
		segTree[i] = 0;
	}
	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 += getCount(0, 0, 2 * n - 1, allPair[i].first, allPair[i].second);
		update(0, allPair[i].second, 0, 2 * n - 1);
	}
	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: 0 / 65