제출 #893677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893677		Darren0724	Monochrome Points (JOI20_monochrome)	C++17	4 / 100	4 ms	3620 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
#define x first
#define y second
const int N=400005;
const int INF=1e18;
const int mod=924844033;
struct BIT{
    vector<int> v=vector<int>(N);
    void add(int p,int t){
        for(int i=p;i<N;i+=i&(-i)){
            v[i]+=t;
        }
    }
    int ask(int p){
        int ans=0;
        for(int i=p;i>0;i-=i&(-i)){
            ans+=v[i];
        }
        return ans;
    }
};
int32_t main() {
    LCBorz;
    int n;cin>>n;
    string s;cin>>s;
    vector<int> a,b;
    for(int i=0;i<n<<1;i++){
        if(s[i]=='W'){
            a.push_back(i+1);
        }
        else{
            b.push_back(i+1);
        }
    }    
    auto solve=[&](int k)->int {
        vector<pair<int,int>> v(n);
        BIT bit;
        for(int i=0;i<n;i++){
            v[i]=make_pair(a[i],b[(i+k)%n]);
            if(v[i].x>v[i].y){
                swap(v[i].x,v[i].y);
            }
            bit.add(v[i].x,1);
            bit.add(v[i].y,-1);
        }
        int ans=0;
        sort(all(v));
        for(int i=0;i<n;i++){
            ans+=bit.ask(v[i].y-1)-bit.ask(v[i].x);
            bit.add(v[i].x,-1);
            bit.add(v[i].y,2);
        }
        return ans;
    };
    int ans=0;
    int l=0,r=n/2+1;
    while(r-l>4){
        int m=(l+r)>>1;
        if(solve(m)>solve(m+1)){
            r=m;
        }
        else{
            l=m;
        }
    }
    for(int i=l;i<=r;i++){
        ans=max(ans,solve(i));
    }
    cout<<ans/2<<endl;

    return 0;
}

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