Submission #1156654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156654		Hamed_Ghaffari	Monochrome Points (JOI20_monochrome)	C++20	35 / 100	2091 ms	7200 KiB

monochrome

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define X first
#define Y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxs(a,b) (a=max(a,b))

const int MXN = (2e5+5)*2;

int fen[MXN];
void updx(int p, int x) {
    for(++p; p<MXN; p+=p&-p) fen[p] += x;
}
int getx(int p) {
    int res=0;
    for(++p; p; p-=p&-p) res += fen[p];
    return res;
}

int n;
vector<int> B, W;

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i=0; i<n+n; i++) {
        char c;
        cin >> c;
        (c=='B' ? B : W).pb(i);
    }
    ll ans=0;
    for(int i=0; i<n; i++) {
        vector<pii> vec;
        for(int j=0; j<n; j++)
            vec.pb({min(B[j], W[(j+i)%n]), max(B[j], W[(j+i)%n])});
        sort(all(vec), greater<>());
        ll res=0;
        for(int j=0; j<n; j++) {
            res += getx(vec[j].Y);
            updx(vec[j].X, 1);
            updx(vec[j].Y+1, -1);
        }
        maxs(ans, res);
        for(int j=0; j<n; j++)
            updx(vec[j].X, -1),
            updx(vec[j].Y+1, 1);
    }
    cout << ans << '\n';
    return 0;
}

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