제출 #1315940

#제출 시각아이디문제언어결과실행 시간메모리
1315940the_ZHERJJOOII 2 (JOI20_ho_t2)C++20
100 / 100
18 ms5960 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int inf=1e18;
const int N=2e5+100;
const int mod=1e9+7;
int a[N],b[N];
pair<int,int>p[N];
int pr[N];
int pr1[N];
int pr2[N];
signed main(){
    boost;
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='O'){
            pr[i]=1;
        }
        pr[i]+=pr[i-1];
    }
    priority_queue<int>st;
    for(int i=0;i<n;i++){
        if(s[i]=='J'){
            st.push(-i);
        }
        if(st.size()==k+1){
            st.pop();
        }
        if(st.size()!=k){
            pr1[i]=-1;
        }else{
            pr1[i]=st.top()*-1;
        }
    }
    while(st.size()>0){
        st.pop();
    }
    int r1=-1;
    for(int i=n-1;i>=0;i--){
        if(s[i]=='I'){
            st.push(((n-1)-i)*-1);
        }
        if(st.size()==k+1){
            st.pop();
        }
        if(st.size()!=k){
            pr2[i]=-1;
        }else{
            pr2[i]=st.top()*-1;
        }
        if(pr2[i]>=0&&r1==-1){
            r1=i;
        }
    }
    int ans=inf;
    for(int i=0;i<n;i++){
        if(pr1[i]==-1){
            continue;
        }
        int l=i+1,r=r1-1;
        while(l+1<r){
            int mid=(l+r)/2;
            int cnt=pr[mid]-pr[i];
            if(cnt>=k){
                r=mid;
            }else{
                l=mid;
            }
        }
        int cnt=pr[l]-pr[i];
        if(cnt>=k){
            r=l;
        }
        cnt=pr[r]-pr[i];
        if(cnt<k){
            break;
        }
        ans=min(ans,n-pr1[i]-pr2[r+1]-(3*k));
    }
    if(ans==inf){
        cout<<"-1";
    }else{
        cout<<ans;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...