#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;
}
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;
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) {
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 + 1; k < r; ++k) {
ans = max(ans, get(k));
}
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20552 KB |
Output is correct |
3 |
Correct |
10 ms |
20596 KB |
Output is correct |
4 |
Incorrect |
12 ms |
20612 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20552 KB |
Output is correct |
3 |
Correct |
10 ms |
20596 KB |
Output is correct |
4 |
Incorrect |
12 ms |
20612 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20552 KB |
Output is correct |
3 |
Correct |
10 ms |
20596 KB |
Output is correct |
4 |
Incorrect |
12 ms |
20612 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
20564 KB |
Output is correct |
2 |
Correct |
10 ms |
20552 KB |
Output is correct |
3 |
Correct |
10 ms |
20596 KB |
Output is correct |
4 |
Incorrect |
12 ms |
20612 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |