Submission #1000015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000015		IWTIM	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	20 ms	8768 KiB

ho_t2

# include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double 
const int N = 1e6 + 5;
int t,n,k,prefo[N],prefj[N],prefi[N],st,l,r,idx,mid,ans;
string s;
signed main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	cin>>s;
	s="@"+s;
	for(int i=1;i<=n;i++){
		prefj[i]=prefj[i-1]+(s[i]=='J');
		prefo[i]=prefo[i-1]+(s[i]=='O');
		prefi[i]=prefi[i-1]+(s[i]=='I');
	}
	ans=1e9;
	for (int i=1;i<=n;i++) {
		st=i;
		l=i; r=n;
		idx=-1;
		while(l<=r){
			mid=(l+r)/2;
			if(prefj[mid]-prefj[st-1]>=k){
				idx=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		if (idx==-1) break;
		st=idx+1;
		l=st; r=n;
		idx=-1;
		while(l<=r){
			mid=(l+r)/2;
			if(prefo[mid]-prefo[st-1]>=k){
				idx=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		if(idx==-1) break;
		st=idx+1;
		l=st; r=n;
		idx=-1;
		while(l<=r){
			mid=(l+r)/2;
			if(prefi[mid]-prefi[st-1]>=k){
				idx=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		if(idx==-1) break;
		ans=min(ans, idx-i+1-3*k);
	}
	if (ans==1e9) cout<<-1;
	else cout<<ans;
}

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