Submission #244885

#	Time	Username	Problem	Language	Result	Execution time	Memory
244885		maximath_1	JJOOII 2 (JOI20_ho_t2)	C++11	100 / 100	47 ms	2960 KiB

ho_t2

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

int n, k; string s;
int pref[200005][3];

int main(){
	cin >> n >> k;
	cin >> s;

	for(int i = 0; i < n; i ++){
		if(i > 0)
			for(int j = 0; j < 3; j ++)
				pref[i][j] = pref[i-1][j];
		if(s[i] == 'J') pref[i][0] ++;
		if(s[i] == 'O') pref[i][1] ++;
		if(s[i] == 'I') pref[i][2] ++;
	}

	int ans = 2e9;
	for(int i = 0; i < n; i ++){
		int cr = i;
		int lf = cr, rg = n, md;
		for(; lf < rg;){
			md = (lf + rg) / 2;
			if(pref[md][0] - (cr > 0 ? pref[cr - 1][0] : 0) >= k) rg = md;
			else lf = md + 1;
		}
		cr = lf;
		lf = cr, rg = n, md;
		for(; lf < rg;){
			md = (lf + rg) / 2;
			if(pref[md][1] - (cr > 0 ? pref[cr - 1][1] : 0) >= k) rg = md;
			else lf = md + 1;
		}
		cr = lf;
		lf = cr, rg = n, md;
		for(; lf < rg;){
			md = (lf + rg) / 2;
			if(pref[md][2] - (cr > 0 ? pref[cr - 1][2] : 0) >= k) rg = md;
			else lf = md + 1;
		}
		cr = lf;
		if(cr == n) continue;
		ans = min(ans, cr - i + 1 - 3 * k);
	}

	if(ans > n) ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:30:22: warning: right operand of comma operator has no effect [-Wunused-value]
   lf = cr, rg = n, md;
                      ^
ho_t2.cpp:37:22: warning: right operand of comma operator has no effect [-Wunused-value]
   lf = cr, rg = n, md;
                      ^

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