Submission #1234564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234564		antromancap	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	20 ms	4164 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
int n, k, c[N][3];
char a[N];
vector<int> v[3];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		copy(c[i - 1], c[i - 1] + 3, c[i]);
		if (a[i] == 'J') c[i][0]++, v[0].push_back(i);
		if (a[i] == 'O') c[i][1]++, v[1].push_back(i);
		if (a[i] == 'I') c[i][2]++, v[2].push_back(i);
	}
	v[0].push_back(n + 1);
	v[1].push_back(n + 1);
	v[2].push_back(n + 1);

	int res = N;
	for (int i = 1; i <= n; i++) {
		if (a[i] != 'J') continue;
		int l = i, r = n;
		while (l <= r) {
			int m = (l + r) >> 1;
			if (c[m][0] - c[i - 1][0] >= k) r = m - 1;
			else l = m + 1;
		}
		if (l > n) continue;
		l = v[1][lower_bound(v[1].begin(), v[1].end(), l) - v[1].begin()];
		int l2 = l, r2 = n;
		while (l2 <= r2) {
			int m = (l2 + r2) >> 1;
			if (c[m][1] - c[l - 1][1] >= k) r2 = m - 1;
			else l2 = m + 1;
		}
		if (l2 > n) continue;
		l2 = v[2][lower_bound(v[2].begin(), v[2].end(), l2) - v[2].begin()];
		int l3 = l2, r3 = n;
		while (l3 <= r3) {
			int m = (l3 + r3) >> 1;
			if (c[m][2] - c[l2 - 1][2] >= k) r3 = m - 1;
			else l3 = m + 1;
		}
		if (l3 > n) continue;
		res = min(res, l3 - i + 1 - 3 * k);
	}
	cout << (res == N ? -1 : res);
}

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