Submission #793991

#TimeUsernameProblemLanguageResultExecution timeMemory
793991acatmeowmeowJJOOII 2 (JOI20_ho_t2)C++11
100 / 100
26 ms5500 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 2e5;
int n, k, prefix[3][N + 5];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	string s;
	cin >> s;
	while (s.size() && s.back() != 'I') s.pop_back();
	reverse(s.begin(), s.end());
	while (s.size() && s.back() != 'J') s.pop_back();
	reverse(s.begin(), s.end());
	n = s.size();
	for (int i = 1; i <= n; i++) {
		int v = s[i - 1] == 'J' ? 0 : (s[i - 1] == 'O' ? 1 : 2);
		prefix[v][i]++;
		for (int j = 0; j < 3; j++) prefix[j][i] += prefix[j][i - 1];
	}
	int ans = 1e18;
	for (int i = 1; i <= n; i++) {
		int l = 1, r = i, lefO = -1;
		while(l <= r) {
			int m = (l + r)/2;
			if (prefix[1][i] - prefix[1][m - 1] >= k) lefO = m, l = m + 1;
			else r = m - 1;
		}
		if (lefO == -1) continue;
		l = 1, r = lefO - 1;
	    int	lefJ = -1;
		while (l <= r) {
			int m = (l + r)/2;
			if (prefix[0][lefO - 1] - prefix[0][m - 1] >= k) lefJ = m, l = m + 1;
			else r = m - 1;
		}
		if (lefJ == -1) continue;
		l = i + 1, r = n;
		int rigI = -1;
		while (l <= r) {
			int m = (l + r)/2;
			if (prefix[2][m] - prefix[2][i] >= k) rigI = m, r = m - 1;
			else l = m + 1;
		}
		if (rigI == -1) continue;
		ans = min(ans, rigI - lefJ + 1 - 3*k);
	}
	cout << (ans == 1e18 ? -1 : ans) << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...