Submission #207837

#TimeUsernameProblemLanguageResultExecution timeMemory
207837pavementJJOOII 2 (JOI20_ho_t2)C++17
100 / 100
34 ms3064 KiB
#include <bits/stdc++.h>
using namespace std;

int N, K, A = 1e9, C[5][200005];
char S[200005];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> S[i];
	for (int i = N; i >= 1; i--) {
		C[1][i] = C[1][i + 1];
		C[2][i] = C[2][i + 1];
		C[3][i] = C[3][i + 1];
		if (S[i] == 'J') C[1][i]++;
		else if (S[i] == 'O') C[2][i]++;
		else C[3][i]++;
	}
	for (int i = 1; i <= N; i++) {
		int lo = 1, hi = i - K + 1, ans = -1, cans;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (C[3][mid] - C[3][i + 1] >= K) ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		if (ans == -1) continue;
		lo = 1, hi = ans - K + 1, cans = ans, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (C[2][mid] - C[2][cans + 1] >= K) ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		if (ans == -1) continue;
		lo = 1, hi = ans - K + 1, cans = ans, ans = -1;
		while (lo <= hi) {
			int mid = (lo + hi) >> 1;
			if (C[1][mid] - C[1][cans + 1] >= K) ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		if (ans == -1) continue;
		A = min(A, i - ans + 1);
	}
	cout << (A == 1e9 ? -1 : A - 3 * K) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...