Submission #807473

#	Time	Username	Problem	Language	Result	Execution time	Memory
807473		OrazB	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	13 ms	3192 KiB

ho_t2

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

const int N = 2e5+5;
int n, k, p[N][3];
string s;

int F(int i, int t){
	if (i == -1) return -1;
	int l = i, r = n, pos = -1;
	while(l <= r){
		int md = (l+r)>>1;
		if (p[md][t]-p[i][t] < k) l = md + 1;
		else{
			pos = md;
			r = md - 1;
		}
	}
	return pos;
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k >> s;
	s = '#' + s;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < 3; j++) p[i][j] = p[i-1][j];
		if (s[i] == 'J') p[i][0]++;
		if (s[i] == 'O') p[i][1]++;
		if (s[i] == 'I') p[i][2]++;
	}
	const int inf = 1e9;
	int mn = inf;
	for (int i = 1; i <= n; i++){
		if (s[i] != 'J') continue;
		int r = F(F(F(i-1, 0), 1), 2);
		if (r == -1) continue;
		mn = min(mn, (r-i+1)-3*k);
	}
	if (mn == inf) mn = -1;
	cout << mn; 
}	

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