/* Ignore Others Only Focus On Yourself! */
/* Im the Best! */
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
const int N = 4e5 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
mt19937 rng(time(nullptr));
int n, fen[N];
void add(int i, int x)
{
for(i += 3; i < N; i += i & -i)
{
fen[i] += x;
}
}
int get(int i, int ret = 0)
{
for(i += 3; i; i -= i & -i)
{
ret += fen[i];
}
return ret;
}
string s;
vector < int > W, B;
vector < pii > seg;
ll tot;
void solve(int Shift)
{
ll ret = 0;
memset(fen, 0, sizeof fen);
seg.clear();
for(int i = 0; i < n; i ++)
{
int j = (i + Shift) % n;
seg.push_back(Mp(max(W[i], B[j]), min(W[i], B[j])));
}
sort(all(seg));
for(int i = 0; i < n; i ++)
{
int l = seg[i].S;
int now = get(l) - (lower_bound(all(seg), Mp(l + 1, -1)) - seg.begin());
ret += now;
add(l, 1);
}
tot = max(tot, ret);
}
int main()
{
fast_io;
cin >> n >> s;
for(int i = 0; i < n << 1; i ++)
{
if(s[i] == 'W')
{
W.push_back(i);
}
else
{
B.push_back(i);
}
}
for(int i = max(0, (n >> 1) - 100); i < min(n, (n >> 1) + 100); i ++)
{
solve(i);
}
cout << tot;
return 0;
}
/* check corner case(n = 1?), watch for negetive index or overflow */
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
1 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
1 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
13 ms |
1876 KB |
Output is correct |
15 |
Correct |
12 ms |
1876 KB |
Output is correct |
16 |
Correct |
13 ms |
1912 KB |
Output is correct |
17 |
Correct |
13 ms |
1904 KB |
Output is correct |
18 |
Correct |
14 ms |
1876 KB |
Output is correct |
19 |
Correct |
12 ms |
1900 KB |
Output is correct |
20 |
Correct |
16 ms |
1880 KB |
Output is correct |
21 |
Correct |
14 ms |
1896 KB |
Output is correct |
22 |
Correct |
14 ms |
1904 KB |
Output is correct |
23 |
Correct |
10 ms |
1896 KB |
Output is correct |
24 |
Correct |
11 ms |
1900 KB |
Output is correct |
25 |
Correct |
13 ms |
1896 KB |
Output is correct |
26 |
Incorrect |
11 ms |
1896 KB |
Output isn't correct |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
1 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
13 ms |
1876 KB |
Output is correct |
15 |
Correct |
12 ms |
1876 KB |
Output is correct |
16 |
Correct |
13 ms |
1912 KB |
Output is correct |
17 |
Correct |
13 ms |
1904 KB |
Output is correct |
18 |
Correct |
14 ms |
1876 KB |
Output is correct |
19 |
Correct |
12 ms |
1900 KB |
Output is correct |
20 |
Correct |
16 ms |
1880 KB |
Output is correct |
21 |
Correct |
14 ms |
1896 KB |
Output is correct |
22 |
Correct |
14 ms |
1904 KB |
Output is correct |
23 |
Correct |
10 ms |
1896 KB |
Output is correct |
24 |
Correct |
11 ms |
1900 KB |
Output is correct |
25 |
Correct |
13 ms |
1896 KB |
Output is correct |
26 |
Incorrect |
11 ms |
1896 KB |
Output isn't correct |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1876 KB |
Output is correct |
3 |
Correct |
1 ms |
1876 KB |
Output is correct |
4 |
Correct |
1 ms |
1876 KB |
Output is correct |
5 |
Correct |
1 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
1876 KB |
Output is correct |
7 |
Correct |
1 ms |
1876 KB |
Output is correct |
8 |
Correct |
1 ms |
1876 KB |
Output is correct |
9 |
Correct |
1 ms |
1876 KB |
Output is correct |
10 |
Correct |
1 ms |
1876 KB |
Output is correct |
11 |
Correct |
1 ms |
1876 KB |
Output is correct |
12 |
Correct |
1 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
13 ms |
1876 KB |
Output is correct |
15 |
Correct |
12 ms |
1876 KB |
Output is correct |
16 |
Correct |
13 ms |
1912 KB |
Output is correct |
17 |
Correct |
13 ms |
1904 KB |
Output is correct |
18 |
Correct |
14 ms |
1876 KB |
Output is correct |
19 |
Correct |
12 ms |
1900 KB |
Output is correct |
20 |
Correct |
16 ms |
1880 KB |
Output is correct |
21 |
Correct |
14 ms |
1896 KB |
Output is correct |
22 |
Correct |
14 ms |
1904 KB |
Output is correct |
23 |
Correct |
10 ms |
1896 KB |
Output is correct |
24 |
Correct |
11 ms |
1900 KB |
Output is correct |
25 |
Correct |
13 ms |
1896 KB |
Output is correct |
26 |
Incorrect |
11 ms |
1896 KB |
Output isn't correct |
27 |
Halted |
0 ms |
0 KB |
- |