Submission #639567

#	Time	Username	Problem	Language	Result	Execution time	Memory
639567		valerikk	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2080 ms	39564 KiB

monochrome

#include <bits/stdc++.h>

using namespace std;

struct Fenwick {
	int sz;
	vector<int> f;

	void add(int i, int val) {
		for (++i; i <= sz; i += i & -i) {
			f[i] += val;
		}
	}

	int calc(int i) {
		int res = 0;
		for (; i > 0; i -= i & -i) {
			res += f[i];
		}
		return res;
	}

	Fenwick(int sz_) : sz(sz_) {
		f.resize(sz + 1, 0);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	string s;
	cin >> n >> s;
	vector<int> black, white;
	for (int i = 0; i < 2 * n; ++i) {
		if (s[i] == 'W') {
			white.push_back(i);
		} else {
			black.push_back(i);
		}
	}
	sort(black.begin(), black.end());
	sort(white.begin(), white.end());
	auto calc = [&](int k) {
		k %= n;
		vector<vector<int>> start(2 * n + 1), finish(2 * n + 1);
		Fenwick fenw(2 * n);
		vector<pair<int, int>> segments;
		for (int i = 0; i < n; ++i) {
			int x = black[i], y = white[(i + k) % n];
			segments.push_back({min(x, y), max(x, y)});
		}
		for (int i = 0; i < n; ++i) {
			start[segments[i].first + 1].push_back(i);
			finish[segments[i].second].push_back(i);
		}
		long long res = 0;
		for (int i = 0; i < 2 * n; ++i) {
			for (int j : start[i]) {
				fenw.add(segments[j].first, 1);
			}
			for (int j : finish[i]) {
				fenw.add(segments[j].first, -1);
			}
			for (int j : finish[i]) {
				res += fenw.calc(2 * n) - fenw.calc(segments[j].first + 1);
			}
		}
		return res;
	};
	if (n == 1) {
		cout << calc(0) << endl;
		return 0;
	}
	vector<int> f(n + 1);
	for (int i = 0; i < n + 1; ++i) {
		f[i] = i % n;
	}
	vector<long long> mem(n + 1, -1);
	auto get = [&](int x) {
		return mem[x] == -1 ? mem[x] = calc(f[x]) : mem[x];
	};
	if (get(0) < get(1)) {
		reverse(f.begin() + 1, f.end());
	}
	int l = 0, r = n;
	while (r - l > 1) {
		int m = (l + r) / 2;
		if (get(m) < get(0)) {
			l = m;
		} else {
			r = m;
		}
	}
	r = n;
	while (r - l > 2) {
		int m = (l + r) / 2;
		if (get(m) < get(m + 1)) {
			l = m;
		} else {
			r = m + 1;
		}
	}
	long long ans = 0;
	for (int k = l; k <= r; ++k) {
		ans = max(ans, get(k));
	}
	cout << ans << endl;
	return 0;
}

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