Submission #1156658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156658		Hamed_Ghaffari	Monochrome Points (JOI20_monochrome)	C++20	100 / 100	922 ms	10404 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))
#define mid ((l+r)>>1)

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

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

int n;
vector<int> B, W;
ll cache[MXN];

inline ll get(int i)  {
    if(cache[i] != -1) return cache[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);
    }
    for(int j=0; j<n; j++)
        updx(vec[j].X, -1),
        updx(vec[j].Y+1, 1);
    return cache[i] = res;
}

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);
    }
    memset(cache, -1, sizeof(cache));
    int l=0, r=n;
    while(l<r)
        if(get(mid)<get(0)) (get(0)>get(1) ? l=mid+1 : r=mid-1);
        else (get(mid)<get(mid+1) ? l=mid+1 : r=mid);
    cout << get(l) << '\n';
    return 0;
}

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