Submission #639563

#	Time	Username	Problem	Language	Result	Execution time	Memory
639563		valerikk	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2057 ms	37116 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 get(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 get = [&](int k) {
		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.get(2 * n) - fenw.get(segments[j].first + 1);
			}
		}
		return res;
	};
	long long ans = 0;
	for (int k = 0; k < n; ++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