Submission #527641

#	Time	Username	Problem	Language	Result	Execution time	Memory
527641		ajpiano	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2089 ms	4280 KiB

monochrome

//https://oj.uz/problem/view/JOI20_monochrome
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;

struct bit{
    vector<int> fen;
    int sz = 0;
    bit (int n){
        sz = n+5; fen.resize(sz);
    }

    void add(int pos){
        pos++;
        for(; pos < sz; pos += pos&-pos) fen[pos]++;
    }

    int asum(int pos){
        pos++;
        int ans = 0;
        for(; pos > 0; pos -= pos&-pos) ans += fen[pos];
        return ans;
    }
    int sum(int l, int r){
        return asum(r)-asum(l);
    }
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    string s; cin >> s;
    vector<int> pb(n), pw(n);
    int b = 0, w  = 0;
    for(int i = 0; i < 2*n; i++){
        if(s[i] == 'B') pb[b++] = i;
        else pw[w++] = i;
    }
    int fans = 0;
    for(int skip = 0; skip < n; skip++){
        b = 0, w = 0;
        bit ssum(2*n);
        int ans = 0;
        for(int i = 0; i < 2*n; i++){
            int goal = 0;
            if(s[i] == 'B'){
                goal = b-skip;
                if(goal < 0) goal += n;
                goal = pw[goal];
                b++;
            }else{
                goal = w+skip;
                if(goal >= n) goal -= n;
                goal = pb[goal];
                w++;
            }
            if(goal < i) continue;
            ans += ssum.sum(i,goal);
            ssum.add(goal);
        }
        fans = max(fans, ans);
    }
    cout << fans << "\n";
    return 0;
}

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