Submission #222501

#	Time	Username	Problem	Language	Result	Execution time	Memory
222501		astoria	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	27 ms	4172 KiB

ho_t2

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

int main(){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	s = 'K'+s;
	vector<int> jpos,ipos;
	int oct[n]; oct[0] = 0;
	int mpj[n], mpi[n];
	memset(mpj,-1,sizeof(mpj)); memset(mpi,-1,sizeof(mpi));
	for(int i=1; i<=n; i++){
		if(s[i]=='J'){ jpos.push_back(i); mpj[i] = jpos.size()-1;}
		if(s[i]=='I'){ ipos.push_back(i); mpi[i] = ipos.size()-1;}
		if(s[i]=='O') oct[i]=oct[i-1]+1;
		else oct[i]=oct[i-1];
	}
	
	int min_span = 1e9;
	int jsz=jpos.size(),isz=ipos.size();
	int j_r = jpos[jsz-1], j_l = jpos[jsz-k];
	int i_l=-1,i_r=-1;
	for(int i=j_r+1; i<=n; i++){
		if(oct[i-1]-oct[j_r]>=k && s[i]=='I'){
			i_l = i; break;
		}
	}
	if(i_l != -1){
		if(mpi[i_l] + k <= isz) i_r = ipos[mpi[i_l]+k-1];
	}
	if(i_r!=-1) min_span = min(min_span, i_r-j_l+1);
	//cout<<min_span<<endl;
	for(int i=jsz-k-1; i>=0; i--){
		j_l = jpos[i]; j_r = jpos[i+k-1];
		//cout<<j_l<<' '<<j_r<<endl;
		if(i_l==-1){
			if(oct[ipos[isz-1]-1] - oct[j_r] >= k) i_l=ipos[isz-1];
			else continue;
		}
		int ival=0;
		for(int v=i_l; v>0; v--){
			if(oct[v-1] - oct[j_r] < k){ ival=v; break;}
		}
		//binse
		
		int llll=1, rrrr=n;
		while(llll<rrrr){
			int mmmm = (llll+rrrr)/2;
			if(oct[mmmm]-oct[j_r] >= k) rrrr=mmmm;
			else llll=mmmm+1;
		}
		ival=llll-1;
		
		
		//binse(ival+1);
		
		int lll=0, rrr=isz-1;
		while(lll<rrr){
			int mmm = (lll+rrr)/2;
			if(ipos[mmm] > ival) rrr=mmm;
			else lll=mmm+1;
		}
		i_l = ipos[lll];
		
		if(i_l != -1){
			if(mpi[i_l] + k <= isz) i_r = ipos[mpi[i_l]+k-1];
		}
		//cout<<i_l<<' '<<i_r<<endl;
		//cout<<mpi[i_l]<<endl;
		if(i_r!=-1) min_span = min(min_span, i_r-j_l+1);
		//cout<<min_span<<endl;
	}
	//cout<<min_span<<endl;
	if(min_span==1e9) cout<<-1;
	else cout<<(min_span-(3*k));
}

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