Submission #800602

#	Time	Username	Problem	Language	Result	Execution time	Memory
800602		Dan4Life	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2037 ms	6168 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
const int N = (int)4e5+10;
int n, fen[N], st[N];
string s;
 
void upd(int x, int v){
    for(; x<N; x+=x&-x) fen[x]+=v;
}
int sum(int x){
    int s=0; for(; x>0; x-=x&-x)s+=fen[x]; return s;
}
int sum(int a, int b){
    return (a<=b)*(sum(b)-sum(a-1));
}
int main()
{
	cin >> n >> s; vector<int> v[2]; int ss = 0;
    for(int i = 0; i < 2*n; i++) v[s[i]=='B'].push_back(i+1);
    for(int k = 0; k < n; k++){
        int ans = 0;
        for(int i = 1; i <= 2*n; i++) st[i]=0;
        for(int i = 0; i < n; i++){
            int a = v[0][i], b = v[1][(i+k)%n];
            if(a>b) swap(a,b);
            st[a] = a; st[b]=a;
        }
        for(int i = 1; i <= 2*n; i++){
            if(st[i]==i) upd(st[i],1);
            else ans+=sum(st[i]+1,i), upd(st[i],-1);
        }
        ss = max(ans, ss);
    }
    cout << ss;
}

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