Submission #793991

#	Time	Username	Problem	Language	Result	Execution time	Memory
793991		acatmeowmeow	JJOOII 2 (JOI20_ho_t2)	C++11	100 / 100	26 ms	5500 KiB

ho_t2

#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;
}

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