Submission #1141045

#TimeUsernameProblemLanguageResultExecution timeMemory
1141045the_coding_poohMonochrome Points (JOI20_monochrome)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

#define fs first
#define sc second

const int SIZE = 2e5 + 5;

string S;

deque <int> pos[2];

vector <pair<int, int>> seg;

int BITree[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;
}

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    int N;
    cin >> N >> S;
    for (int i = N; i < S.size(); i++){
        pos[S[i] == 'W'].push_back(i);
    }
    for (int i = 0; i < N; i++){
        seg.push_back({i, pos[S[i] == 'B'].front()});
        pos[S[i] == 'B'].pop_front();
    }
    long long ans = 0;
    for (int i = 0; i < N; i++){
        ans += query(seg[i].sc);
        modify(seg[i].sc, 1);
    }
    cout << ans << '\n';
    uwu
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...