Submission #639571

#	Time	Username	Problem	Language	Result	Execution time	Memory
639571		valerikk	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	1198 ms	54140 KiB

monochrome

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 7;

int fen[N];
vector<int> start[N], finish[N];

void add_fen(int i, int val) {
	for (++i; i < N; i += i & -i) {
		fen[i] += val;
	}
}

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

char s[N];

int main() {
	int n;
	scanf("%d", &n);
	scanf("%s", 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;
		for (int i = 0; i < 2 * n + 1; ++i) {
			start[i].clear();
			finish[i].clear();
		}
		memset(fen, 0, sizeof fen);
		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;
		int tot = 0;
		for (int i = 0; i < 2 * n; ++i) {
			for (int j : start[i]) {
				++tot;
				add_fen(segments[j].first, 1);
			}
			for (int j : finish[i]) {
				--tot;
				add_fen(segments[j].first, -1);
			}
			for (int j : finish[i]) {
				res += tot - get_fen(segments[j].first + 1);
			}
		}
		return res;
	};
	if (n == 1) {
		printf("%lld\n", calc(0));
		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));
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
monochrome.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%s", s);
      |  ~~~~~^~~~~~~~~

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