Submission #1141091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141091		the_coding_pooh	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	1640 ms	4312 KiB

monochrome

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

#define fs first
#define sc second

const int SIZE = 2e5 + 5, MAGIC = 10;

string S;

deque <int> pos[2];

vector <int> seg;

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 eval(int x, int N){
    if(x < 0 || x >= 2 * N)
        return 0;
    for (int i = 0; i < 2 * N; i++){
        BITree[i] = 0;
    }
    seg.clear();
    pos[0].clear();
    pos[1].clear();
    for (int i = N; i < S.size(); i++){
        pos[S[(i + x) % (2 * N)] == 'W'].push_back(i);
    }
    for (int i = 0; i < N; i++){
        seg.push_back(pos[S[(i + x) % (2 * N)] == 'B'].front());
        pos[S[(i + x) % (2 * N)] == 'B'].pop_front();
    }
    long long ans = 0;
    for (int i = 0; i < N; i++){
        ans += query(seg[i]);
        modify(seg[i], 1);
    }
    return ans;
}

long long vv[2 * SIZE];

long long ev(int x, int N){
    if(vv[x])
        return vv[x];
    for (int i = MAGIC * x; i < MAGIC * (x + 1); i++){
        vv[x] = max(eval(i, N), vv[x]);
    }
    return vv[x];
}

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    int N;
    cin >> N >> S;
    long long water_line = ev(0, N);
    if(ev(1, N) > water_line){
        int L = 0, R = (2 * N - 1) / MAGIC, M, M1, M2;
        while (L != R){
            M = (L + R + 1) / 2;
            if(ev(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(ev(M1, N) < ev(M2, N))
                L = M1 + 1;
            else
                R = M2 - 1;
        }
        cout << max(water_line, ev(L, N)) << '\n';
    }
    else{
        int L = 0, R = (2 * N) / MAGIC, M, M1, M2;
        while (L != R){
            M = (L + R) / 2;
            if(ev(M, N) < water_line)
                L = M + 1;
            else
                R = M;
        }
        R = (2 * N - 1) / MAGIC;
        while(L != R){
            M1 = L + (R - L) / 3;
            M2 = R - (R - L) / 3;
            if(ev(M1, N) < ev(M2, N))
                L = M1 + 1;
            else
                R = M2 - 1;
        }
        cout << max(water_line, ev(L, N)) << '\n';
    }
    uwu
}

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