제출 #1140466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140466		browntoad	Monochrome Points (JOI20_monochrome)	C++20	0 / 100	1 ms	1864 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

const ll maxn = 2e5+5;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;

vector<int> bit(maxn);
int quer(int a){
    int ret = 0;
    while(a > 0){
        ret += bit[a];
        a -= (a&-a);
    }
    return ret;
}
void modify(int a){
    while(a < maxn){
        bit[a]++;
        a += (a&-a);
    }
}


int n;
int run(string str){
    vector<int> bs, ws;
    REP(i, n){
        if (str[i] == 'B') bs.pb(i+1); // 1-base
        else ws.pb(i+1);
    }
    int bptr = 0, wptr = 0;

    vector<int> ret(n);
    FOR(i, n, 2*n){
        if (str[i] == 'B') ret[i-n] = ws[wptr++];
        else ret[i-n] = bs[bptr++];
    }

    int ans = 0;
    REP(i, n){
        ans += quer(ret[i]);
        modify(ret[i]);
    }
    return ans;
}
signed main(){
    //IOS();
    cin>>n;
    string str; cin>>str;
    cout<<run(str)<<endl;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65