제출 #1143081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143081		owoovo	Monochrome Points (JOI20_monochrome)	C++20	100 / 100	749 ms	10336 KiB

monochrome

#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
struct BIT{
    ll val[400010];
    void init(){
        for(int i=1;i<=400005;i++)val[i]=0;
    }
    void modify(int p,ll x){
        while(p<400005){
            val[p]+=x;
            p+=p&(-p);
        }
    }
    ll query(int p){
        ll ans=0;
        while(p){
            ans+=val[p];
            p-=p&(-p);
        }
        return ans;
    }
}bit;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll ans=0;
    int n;
    cin>>n;
    vector<int> tp,o,x;
    for(int i=1;i<=n*2;i++){
        char c;
        cin>>c;
        if(c=='W'){
            tp.push_back(i);
        }else{
            x.push_back(i);
        }
    }
    for(auto u:tp)o.push_back(u);
    for(auto u:tp)o.push_back(u);
    map<int,ll> mp;
    auto cal=[&](int i){
        if(mp.count(i)){
            return mp[i];
        }
        vector<pair<int,int>> op;
        for(int j=0;j<n;j++){
            int a=x[j],b=o[i+j];
            //cout<<"pair "<<a<<" "<<b<<'\n';
            if(a>b)swap(a,b);
            op.push_back({a,b});
        }
        sort(op.begin(),op.end());
        reverse(op.begin(),op.end());
        bit.init();
        ll now=0;
        queue<int> q;
        for(auto [a,b]:op){
            now+=bit.query(b);
            bit.modify(b+1,-1);
            bit.modify(a,1);
        }
        mp[i]=now;
        //cout<<i<<" "<<now<<"\n";
        return now;
    };
    int l=0,r=n,rv=(cal(0)>cal(1)),water=cal(0);
    while(l!=r){
        int m=(l+r)>>1;
        if(cal(m)<water){
            if(rv){
                l=m+1;
            }else{
                r=m-1;
            }
        }else{
            if(cal(m)<cal(m+1))l=m+1;
            else r=m;
        }
    }
    cout<<cal(l)<<"\n";

    return 0;
}

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