Submission #861189

#	Time	Username	Problem	Language	Result	Execution time	Memory
861189		dsyz	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	9 ms	5860 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,K;
	cin>>N>>K;
	string s;
	cin>>s;
	ll Opsum[N];
	ll cur = 0;
	for(ll i = 0;i < N;i++){
		if(s[i] == 'O'){
			cur++;
		}
		Opsum[i] = cur;
	}
	ll Jpre[N];
	cur = 0;
	ll ptr = 0;
	for(ll r = 0;r < N;r++){
		if(s[r] == 'J'){
			cur++;
		}
		while(ptr < r && (cur > K || s[ptr] != 'J')){
			if(s[ptr] == 'J') cur--;
			ptr++;
		}
		if(cur >= K) Jpre[r] = ptr;
		else Jpre[r] = -1;
	}
	
	ll Isuf[N];
	cur = 0;
	ptr = N - 1;
	for(ll l = N - 1;l >= 0;l--){
		if(s[l] == 'I'){
			cur++;
		}
		while(ptr > l && (cur > K || s[ptr] != 'I')){
			if(s[ptr] == 'I') cur--;
			ptr--;
		}
		if(cur >= K) Isuf[l] = ptr;
		else Isuf[l] = -1;
	}
	
	ll L = 1;
	ll R = 1;
	bool ok = 0;
	ll ans = 1e18;
	while(R < N - 1){
		while(L < R && Opsum[R] - Opsum[L] >= K){
			L++;
		}
		if(Jpre[L - 1] != -1 && Isuf[R + 1] != -1 && Opsum[R] - Opsum[L - 1] >= K){
			ok = 1;
			ans = min(ans,(Isuf[R + 1] - Jpre[L - 1] + 1) - 3 * K);
		}
		R++;
	}
	if(!ok){
		cout<<-1<<'\n';
	}else{
		cout<<ans<<'\n';
	}
}

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