Submission #362274

#	Time	Username	Problem	Language	Result	Execution time	Memory
362274		doowey	Monochrome Points (JOI20_monochrome)	C++14	35 / 100	2093 ms	10964 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 = 0;
    for(int i = 0 ; i < n; i ++ ){
        high = max(high, f(i));
    }
    cout << high << "\n";
    return 0;
}

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