Submission #1141288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141288		the_coding_pooh	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	2093 ms	11204 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 = 12;

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 eval(int x, int N){
    x %= N;
    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 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)
    //             L = M + 1;
    //         else
    //             R = M;
    //     }
    //     R = N - 1;
    //     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';
    // }
    long long ans = 0;
    for (int i = 0; i < N; i++){
        ans = max(ans, eval(i, N));
    }
    cout << ans << '\n';
    uwu
}

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