Submission #244868

#	Time	Username	Problem	Language	Result	Execution time	Memory
244868		vioalbert	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	17 ms	2768 KiB

ho_t2

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

const int N = 2e5+5;
int n, k;
int prefJ[N], prefO[N], prefI[N];

void read() {
	cin >> n >> k;
	prefJ[0] = prefO[0] = prefI[0] = 0;
	for(int i = 1; i <= n; i++) {
		char c; cin >> c;
		prefJ[i] = prefJ[i-1] + (c == 'J');
		prefO[i] = prefO[i-1] + (c == 'O');
		prefI[i] = prefI[i-1] + (c == 'I');
	}
}

int binserO(int l, int r) {
	int d = l-1;
	while(l < r) {
		int mid = (l+r)/2;
		if(prefO[mid] - prefO[d] < k) l = mid+1;
		else r = mid;
	}
	return l;
}

int binserI(int l, int r) {
	int d = l-1;
	while(l < r) {
		int mid = (l+r)/2;
		if(prefI[mid] - prefI[d] < k) l = mid+1;
		else r = mid;
	}
	return l;
}

void solve() {
	int ans = 1e9;
	int fp = 0, prv = 0;
	for(int i = 1; i <= n; i++) {
		if(prv < prefJ[i] && prefJ[i] >= k) {
			while(prefJ[fp] <= prefJ[i] - k) fp++;
			int mp = binserO(i+1, n+1);
			if(mp == n+1) break;
			int lp = binserI(mp+1, n+1);
			if(lp == n+1) break;
			ans = min(ans, lp - fp + 1 - 3*k);
		}
		prv = prefJ[i];
	}
	cout << ((ans==1e9)?(-1):ans) << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read(); solve();
	return 0;
}

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