Submission #888164

#	Time	Username	Problem	Language	Result	Execution time	Memory
888164		Unforgettablepl	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	21 ms	5340 KiB

ho_t2

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

#define int long long
const int INF = INT64_MAX;

int prefix[200001][3];

int32_t main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        char a;cin>>a;
        prefix[i][0]=prefix[i-1][0];
        prefix[i][1]=prefix[i-1][1];
        prefix[i][2]=prefix[i-1][2];
        if(a=='J')prefix[i][0]++;
        else if(a=='O')prefix[i][1]++;
        else prefix[i][2]++;
    }
    int ans = INF;
    for(int l=1;l<=n;l++){
        if(prefix[l][0]-prefix[l-1][0]==0)continue;
        if(prefix[n][0]-prefix[l-1][0]<k)break;
        int mid1 = l-1;
        for(int jump=131072;jump;jump/=2){
            if(mid1+jump>n)continue;
            if(prefix[mid1+jump][0]-prefix[l-1][0]<k)mid1+=jump;
        }
        mid1++;
        if(prefix[n][1]-prefix[mid1-1][1]<k)break;
        int mid2 = mid1-1;
        for(int jump=131072;jump;jump/=2){
            if(mid2+jump>n)continue;
            if(prefix[mid2+jump][1]-prefix[mid1-1][1]<k)mid2+=jump;
        }
        mid2++;
        if(prefix[n][2]-prefix[mid2-1][2]<k)break;
        int r = mid2-1;
        for(int jump=131072;jump;jump/=2){
            if(r+jump>n)continue;
            if(prefix[r+jump][2]-prefix[mid2-1][2]<k)r+=jump;
        }
        r++;
        ans = min(ans,r-l);
    }
    if(ans==INF)cout << "-1\n";
    else cout << ans+1-3*k << '\n';
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87