Submission #1310751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310751		samarthkulkarni	JJOOII 2 (JOI20_ho_t2)	C++20	100 / 100	11 ms	3852 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}




void solution() {
	ll n, k; cin >> n >> k;

	string s; cin >> s;

	while (s.size() > 0 && s.back() != 'I') s.pop_back(); 
	reverse(all(s));
	while (s.size() > 0 && s.back() != 'J') s.pop_back();
	reverse(all(s));
	n = s.size();

	if (!n) {
		cout << -1 << endl;
		return;
	}
 
	s = '0'+s;

	vi ps(n+1), suf(n+2);

	for (int i = 1; i <= n; i++) ps[i] = ps[i-1] + (s[i] == 'J');

	for (int i = n; i >= 1; i--) suf[i] = suf[i+1] + (s[i] == 'I');


	// cout << s << endl;
	ll ans = 1e18;
	int j = 1;
	int cnt = 0;


	for (int i = 1; i <= n; i++) {

		j = max(j, i);
		if (s[i] != 'O') continue;

		while (j <= n && cnt < k) {
			cnt += (s[j] == 'O');
			j++;
		}

		if (cnt != k) continue;
		cnt--;

		ll temp = j-i-k;
		int p = 1, q = i-1;	

		int d = -1;
		while (p <= q) {
			int mid = (p + q)/2;
			if (ps[i]-ps[mid-1] >= k) {
				d = mid;
				p = mid+1;
			} else q = mid-1;
		}

		if (d == -1) continue;
		temp += i-d-k;

		d = -1;
		p = j, q = n;
		while (p <= q) {
			int mid = (p + q)/2;
			if (suf[j]-suf[mid+1] >= k) {
				d = mid;
				q = mid-1;
			} else p = mid+1;
		}

		if (d == -1) continue;

		temp += d - (j-1) - k;

		ans = min(ans, temp);
	}

	cout << (ans == 1e18? -1 : ans) << endl;





}

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