Submission #362275

#	Time	Username	Problem	Language	Result	Execution time	Memory
362275		doowey	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	1814 ms	10952 KiB

monochrome

#include <bits/stdc++.h>

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)4e5 + 100;

int col[N];
int n, m;
vector<int> C[2];
int segt[N*2];

void upd(int id, int v){
    id += m;
    while(id > 0){
        segt[id] += v;
        id /= 2;
    }
}

int get(int l, int r){
    l += m;
    r += m;
    int cum = 0;
    while(l <= r){
        if(l % 2 == 1) cum += segt[l ++ ];
        if(r % 2 == 0) cum += segt[r -- ];
        l /= 2;
        r /= 2;
    }
    return cum;
}

ll f(int k){
    vector<pii> seg;
    for(int i = 0 ; i < n; i ++ ){
        seg.push_back(mp(C[0][i], C[1][(i + k) % n]));
    }
    for(auto &x : seg){
        if(x.fi > x.se) swap(x.fi, x.se);
    }
    for(int i = 0 ; i < m * 2; i ++ ){
        segt[i]=0;
    }
    sort(seg.begin(), seg.end());
    ll ff = 0;
    for(auto q : seg){
        ff += get(q.fi, q.se);
        upd(q.se, +1);
    }
    return ff;
}

int main(){
    fastIO;
    cin >> n;
    m = n * 2;
    char qf;
    for(int i = 0; i < m ; i ++ ){
        cin >> qf;
        if(qf == 'B'){
            col[i]=0;
        }
        else{
            col[i]=1;
        }
        C[col[i]].push_back(i);
    }
    ll high = f(0);
    int li = 1;
    int ri = n;
    int mid;
    while(li < ri){
        mid = (li + ri) / 2;
        if(f(mid) < f(mid + 1)){
            li = mid + 1;
        }
        else{
            ri = mid;
        }
    }
    high = max(high, f(li));
    cout << high << "\n";
    return 0;
}

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