Submission #1088932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088932		Wansur	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	567 ms	5528 KiB

monochrome

#include <bits/stdc++.h>
#define ent '\n'
//#define int long long

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 12;

int t[maxn * 2], r[maxn * 2];
int a[maxn], b[maxn];
int n, m, k;

void upd(int i, int x){
    for(; i <= n * 2;i |= (i + 1)){
        t[i] += x;
    }
}

int GET(int i){
    int ans = 0;
    for(; i > 0; i = (i & (i + 1)) - 1){
        ans += t[i];
    }
    return ans;
}

int get(int l, int r){
    return GET(r) - GET(l - 1);
}

ll get(int k){
    for(int i=1;i<=n*2;i++){
        t[i] = r[i] = 0;
    }
    vector<pair<int, int>> v;
    for(int i=0;i<n;i++){
        r[min(a[i], b[(i + k) % n])] = max(a[i], b[(i + k) % n]);
    }
    ll ans = 0;
    for(int i=1;i<=2 * n;i++){
        if(!r[i]) continue;
        ans += get(i, r[i]);
        upd(r[i], 1);
    }
    return ans;
}

void solve(){
    cin >> n;
    int l = 0, r = 0;
    ll ans = 0;
    for(int i=1;i<=2*n;i++){
        char c;
        cin >> c;
        if(c == 'W') a[l++] = i;
        else b[r++] = i;
    }
    l = 1, r = n;
    while(r - l > 3){
        int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        ll x = get(m1), y = get(m2);
        ans = max({ans, x, y});
        if(x < y) l = m1;
        else r = m2;
    }
    for(int i=l;i<=r;i++){
        ans = max(ans, get(i));
    }
    cout << ans << ent;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
}

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