Submission #502581

#	Time	Username	Problem	Language	Result	Execution time	Memory
502581		amunduzbaev	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	1193 ms	10828 KiB

monochrome

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 4e5 + 5;

struct BIT{
	int tree[N];
	void add(int i, int v){ i++;
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){ i++;
		int rr = 0;
		for(;i>0;i-=(i&-i)) rr += tree[i];
		return rr;
	}
	
	int get(int l, int r){
		return get(r) - get(l-1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	string s; cin>>s;
	ar<vector<int>, 2> p;
	for(int i=0;i<2*n;i++){
		p[s[i] == 'B'].push_back(i);
	}
	
	auto check = [&](int k){
		memset(tree.tree, 0, sizeof tree.tree);
		int res = 0;
		vector<ar<int, 2>> a(n);
		for(int i=0;i<n;i++){
			int j = (i + k) % n;
			a[i] = {p[0][i], p[1][j]};
			if(a[i][0] > a[i][1]) swap(a[i][0], a[i][1]);
		}
		
		sort(a.begin(), a.end());
		for(auto x : a){
			res += tree.get(x[0], x[1]);
			tree.add(x[1], 1);
		} return res;
	};
	
	int l = 0, r = n - 1;
	while(l < r){
		int m = (l + r) >> 1;
		if(check(m) < check(m + 1)) l = m + 1;
		else r = m;
	}
	
	cout<<check(l)<<"\n";
}

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