Submission #770650

#	Time	Username	Problem	Language	Result	Execution time	Memory
770650		nihon	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	11 ms	1616 KiB

ho_t2

#include <bits/stdc++.h>
#define N 200005
using namespace std;
string s;
char ch;
int n,k,i,l,st,dr,mid,sol,b,e,x;
int J[N],O[N],I[N],tj,to,ti;
int mn=2e9;
int main()
{
    cin>>n>>k>>s;
    l=s.size();
    for(i=0;i<l;i++)
    {
        ch=s[i];
        if(ch=='J')
        {
            J[++tj]=i;
        }
        if(ch=='O')
        {
            O[++to]=i;
        }
        if(ch=='I')
        {
            I[++ti]=i;
        }
    }
    for(i=1;i<=tj;i++)
    {
        if(i+k-1>tj) break;
        b=J[i];
        x=J[i+k-1]+1;
        if(x>=l) continue;
        st=1; dr=to; sol=-1;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(O[mid]<x) st=mid+1;
            else {sol=mid; dr=mid-1;}
        }
        if(sol<0 || sol+k-1>to) continue;
        x=O[sol+k-1]+1;
        if(x>=l) continue;
        st=1; dr=ti; sol=-1;
        while(st<=dr)
        {
            mid=(st+dr)>>1;
            if(I[mid]<x) st=mid+1;
            else {sol=mid; dr=mid-1;}
        }
        if(sol<0 || sol+k-1>ti) continue;
        e=I[sol+k-1];
        mn=min(mn,(e-b+1)-3*k);
    }
    if(mn==2e9) cout<<-1;
    else cout<<mn;
    return 0;
}

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