| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1141297 | the_coding_pooh | Monochrome Points (JOI20_monochrome) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define uwu return 0;
#define int long long
using namespace std;
#define fs first
#define sc second
const int SIZE = 2e5 + 5;
string S;
int ps[2][SIZE];
int BITree[2 * SIZE];
void modify(int pos, int val){
for (; pos < SIZE; pos += (pos & - pos)){
BITree[pos] += val;
}
return;
}
int query(int pos){
int ret = 0;
for (; pos; pos -= (pos & - pos)){
ret += BITree[pos];
}
return ret;
}
long long vv[SIZE];
long long eval(int x, int N){
x %= N;
if(vv[x])
return vv[x];
for (int i = 0; i < 2 * N; i++){
BITree[i] = 0;
}
long long ans = 0;
vector <pair<int, int>> seg;
for (int i = 0; i < N; i++){
seg.push_back({ps[0][i], ps[1][(i + x) % N]});
seg.push_back({ps[1][(i + x) % N], ps[0][i]});
}
sort(seg.begin(), seg.end());
for (auto i:seg){
if(i.sc > i.fs){
ans += query(i.sc);
modify(i.sc, 1);
}
else{
modify(i.fs, -1);
}
}
return vv[x] = ans;
}
int main(){
cin.tie(0), ios::sync_with_stdio(0);
int N;
cin >> N >> S;
int ptr[2] = {0, 0};
for (int i = 0; i < 2 * N; i++){
ps[S[i] == 'W'][ptr[S[i] == 'W']++] = i;
}
long long water_line = eval(0, N);
if(eval(1, N) >= water_line){
int L = 0, R = N - 1, M, M1, M2;
while (L != R){
M = (L + R + 1) / 2;
if(eval(M, N) < water_line)
R = M - 1;
else
L = M;
}
L = 0;
while(L != R){
M1 = L + (R - L) / 3;
M2 = R - (R - L) / 3;
if(eval(M1, N) < eval(M2, N))
L = M1 + 1;
else
R = M2 - 1;
}
cout << eval(L, N) << '\n';
}
else{
int L = 0, R = N - 1, M, M1, M2;
while (L != R){
M = (L + R) / 2;
if(eval(M, N) > water_line)
R = M;
else
L = M + 1;
}
R = N;
while(L != R){
M1 = L + (R - L) / 3;
M2 = R - (R - L) / 3;
if(eval(M1, N) < eval(M2, N))
L = M1 + 1;
else
R = M2 - 1;
}
cout << eval(L, N) << '\n';
}
uwu
}