Submission #906425

#	Time	Username	Problem	Language	Result	Execution time	Memory
906425		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	35 ms	8768 KiB

ho_t2

#include<bits/stdc++.h>
#include<queue>
#define ll long long
using namespace std;

ll n, k, dem = 0, cnt[5], pfs[(int)2e5+5][5];

char a[5] = {'J', 'O', 'I'};

string s;

ll bs(ll x, ll y, ll l, ll r){
	
	ll mid;
	
	while(l <= r){
		
		mid = (l+r)/2;
		
		if(pfs[mid][y] >= x + k) r = mid-1;
		
		else l = mid+1;
	}
	return l;
}

int main(){

	ios_base::sync_with_stdio(0);
	
	cin.tie(0);
	
	cin>>n>>k>>s;
	
	s = " "+s;
	
	for(int i = 1; i <= n; i++){
		
		for(int j = 0; j < 3; j++){
			
			if(s[i] == a[j]){
				
				pfs[i][j] = pfs[i-1][j] + 1;
			}
			
			else pfs[i][j] = pfs[i-1][j];
		}
	}
	
//	for(int i = 1; i <= n; i++) cout<<pfs[i][0]<<" ";
//	
//	cout<<endl;
	
	ll start = 1, i, j, ans = 0, x, ds = 1e18;
	
	bool flag = true;
	
	while(flag == true){
		
		i = start;
		
//		cout<<i<<endl;
		
		ans = 0; x = 0;
		
		for(int t = 0; t < 3; t++){
			
			i = bs((-1)*k+1, t, i, n);
			
			if(t == 0) x = i-1;
			
			j = bs(pfs[i-1][t], t, i, n);
			
//			cout<<i<<" "<<j<<" ";
			
			ans += i - x - 1 + j - i + 1 - k;
			
//			cout<<ans<<endl;
			
			if(i > n || j > n){
				
				flag = false;
				
				ans = 1e18;
				
//				cout<<"!! "<<i<<" "<<j;
				
				break;
			}
			
			i = j+1;
			
			x = j;
		}
//		cout<<ans<<endl<<endl;
		
		ds = min(ds, ans);
		
		if(flag == false) break;
		
//		if(start == 3) break;
		
		start++;
	}
	if(ds != 1e18) cout<<ds;
	
	else cout<<-1;
}

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