Submission #1253495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253495		LM1	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	32 ms	3088 KiB

ho_t2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define fr(i,ii,iii) for(int i=ii;i<iii;i++)
const int N=2e5+5;
int n,k;
int c[N][3];
map<char,int>mp;
string a;
int find(int x,int d){
	int l=x,r=n+1,m,ans=-1;
	while(l<r){
		m=(l+r)/2;
		int cn=c[m][d]-c[x-1][d];
		if(cn>=k){
			ans=m;
			r=m;
		}
		else{
			l=m+1;
		}
	}
	return ans;
}
int main(){
	mp['J']=0;
	mp['O']=1;
	mp['I']=2;
	cin>>n>>k>>a;
	a='@'+a;
	int ans=1e6;
	fr(i,1,n+1){
		fr(j,0,3)c[i][j]=c[i-1][j];
		c[i][mp[a[i]]]++;
	}
	fr(i,1,n+1){
		int i1=i;
		fr(j,0,3){
			i1=find(i1,j);
			if(i1==-1)goto end;
		}
		ans=min(ans,i1-i+1-3*k);
	}
	end:;
	cout<<(ans==1e6?-1:ans);
}

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