Submission #1205517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205517		minhpk	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	29 ms	11596 KiB

ho_t2

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
string s;
int prefix[1000005][4];
int nxt[300005][3];
int min1=1e18;
int check(int sta,int i){
    int l=sta;
    int r=a;
    int pos=-1;
    while (l<=r){
         int mid=(l+r)/2;
         if (prefix[mid][i]-prefix[sta-1][i]>=b){
             pos=mid;
             r=mid-1;
         }else{
             l=mid+1;
         }
    }
    return pos;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    cin >> s;
    s='#'+s;
    for (int i=1;i<=a;i++){
         prefix[i][1]=prefix[i-1][1]+(s[i]=='J');
         prefix[i][2]=prefix[i-1][2]+(s[i]=='O');
         prefix[i][3]=prefix[i-1][3]+(s[i]=='I');
    }

    for (int i=1;i<=a;i++){
         nxt[i][1]=check(i,1);
         nxt[i][2]=check(i,2);
         nxt[i][3]=check(i,3);
    }
    for (int i=1;i<=a;i++){
         if (s[i]!='J'){
            continue;
         }
         int l=i;
         int r=i;
         r=nxt[r][1];
         if (r==-1){
            continue;
         }
         r=nxt[r][2];
         if (r==-1){
            continue;
         }
         r=nxt[r][3];
         if (r==-1){
            continue;
         }
         min1=min(min1,r-l+1-3*b);
    }
    if (min1==1e18){
        cout << -1 << "\n";
    }else{
        cout << min1 << "\n";
    }
    return 0;
}

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