이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (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);
| ~~~~~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |